Blowfish

Ο Blowfish προτάθηκε από τον Bruce Schneier στο εργαστήριο ασφαλείας του Κέιμπριτζ το 1993 και είχε ως στόχο να ξεκινήσει την προσπάθεια για τη δημιουργία ενός καλού κρυπτογραφικού συστήματος το οποίο θα άντεχε στους υπολογιστές του 21ου αιώνα, καθώς οι αλγόριθμοι εκείνης της περιόδου είδη είχαν αρχίσει να γίνονται ευάλωτοι σε επιθέσεις. Είναι ένας αλγόριθμος κρυπτογράφησης τμήματος τύπου Feistel στον οποίο χρησιμοποιείται μια συνάρτηση κρυπτογραφίας σε δεκαέξι επαναλήψεις. Σε κάθε επανάληψη κρυπτογραφούνται 64 bits. Το μήκος του κλειδιού μπορεί να έχει μήκος μέχρι και 448 bits. Παρόλα αυτά υπάρχει μια περίπλοκη διαδικασία η οποία πρέπει να γίνει πριν από κάθε κρυπτογράφηση. Ο blowfish είναι ένας αλγόριθμος που χρησιμοποιείται μόνο όταν το κλειδί δεν πρέπει να αλλάζει συχνά (το κλειδί σε ένα πραγματικά ασφαλές σύστημα κρυπτογραφίας πρέπει να αλλάζει ανάλογα με την πολιτική ασφαλείας).

Στοιχεία-εργασίες που μπορεί να κάνει ο blowfish

Περιοχές εφαρμογής

Ο αλγόριθμος είναι αποδοτικός όταν κρυπτογραφεί αρχεία.

Γεννήτρια τυχαίων αριθμών. Ο αλγόριθμος πρέπει να μπορεί να δημιουργεί μοναδικά τυχαία bits.

Κρυπτογράφηση πακέτων. Ο αλγόριθμος είναι αποδοτικός στην κρυπτογράφηση δεδομένων σε μέγεθος πακέτων. Επίσης θα πρέπει να μπορεί να υλοποίηση κρυπτογράφηση και αποκρυπτογράφηση συνεχόμενων πακέτων με διαφορετικό κλειδί.

Κατακερματισμός. Ο αλγόριθμος λειτουργεί και ως μίας φοράς (one way) συνάρτηση κατακερματισμού (hash function).

Συσκευές

Κάθε αλγόριθμος κρυπτογράφησης θα πρέπει να λειτουργεί αποτελεσματικά, ανεξάρτητα σε τι συσκευή υλοποιείται.

Ειδικό hardware. Ο αλγόριθμος θα πρέπει να είναι αποτελεσματικός σε ειδικά επεξεργασμένα VLSI hardware.

Περισσότερες απαιτήσεις

Ο αλγόριθμος θα πρέπει να είναι απλός στην υλοποίηση του για να αποφευχθούν λάθη που θα τον καταστρέψουν από την δημιουργία του. Δεν πρέπει να έχει αδύναμα κλειδιά, πρέπει να έχει εύκολη διακύμανση για διαφορετικά επίπεδα δυσκολίας. Τέλοςλ όλες οι διαχειρίσεις των δεδομένων θα πρέπει να γίνεται σε τμήματα (blocks).

Κατασκευασμένα τμήματα δεδομένων

S-boxes. Τα S-boxes έχουν μεγαλύτερη αντοχή σε μια διαφορική κρυπτοανάλυση, ένας αλγόριθμος με 32 bit μήκος, μπορεί να κάνει χρήση ενός 32 bit S-boxes. Ακόμη για μεγαλύτερη ασφάλεια μπορούν να χρησιμοποιηθούν S-boxes εξαρτημένα από το κλειδί καθώς αυτά έχουν μεγαλύτερες αντοχές σε διαφορικές και γραμμικές αναλύσεις.

Περιγραφή κώδικα blowfish

Ο blowfish είναι ένας αλγόριθμος κρυπτογραφησης τμήματος (block cipher) που κρυπτογραφεί τμήματα μήκους 64 bit. Αποτελείται από δύο μέρη: το πρώτο είναι η επέκταση του κλειδιού (γίνεται η παραγωγή των session keys) στο το δεύτερο το σχήμα Feistel, όπου γίνεται η κρυπτογράφηση (σε κάθε επανάληψη γίνεται η χρηση ενός session key). Η επέκταση του κλειδιού (expansion key algorithm) μετατρέπει το κλειδί σε υποκλειδιά συνολικού μεγέθους 4168 bytes. Η κρυπτογράφηση ενός κειμένου γίνεται μέσα από ένα σύστημα Feistel το οποίο τρέχει για 16 επαναλήψεις. Κάθε γύρος αποτελείται από ένα κλειδί όπου είναι εξαρτημένο από μια μετάθεση του επιτεταμένου κλειδιού και από ένα πακέτο δεδομένων για κρυπτογράφηση.

Όλες οι πράξεις είναι τύπου XOR και προσθέσεις σε 32 bit λέξεων. Οι μοναδικές επιπρόσθετες πράξεις είναι τέσσερις πίνακες όπου κρατάνε δεδομένα και αλλάζουν σε κάθε επενάληψη.

Υποκλειδιά

Ο blowfish επειδή χρειάζεται πολλά υποκλειδιά (όσες είναι οι επαναλήψεις) θα πρέπει όλα να υπολογιστούν πριν ξεκινήσει μια κρυπτογράφηση ή αποκρυπτογράφηση.

1. Το συνολικό κλειδί χωρίζεται σε 18 κομμάτια των 32 bit:

P₁,P₂,…,P₁₈

1. Οι τέσσερεις πίνακες έχουν 256 καταχωρίσεις το κάθε ένα:

S_1,0,S_1,1,…,S_1,255

S_2,0,S_2,1,…,S_2,255

S_3,0,S_3,1,…,S_3,255

S_4,0,S_4,1,…,S_4,255

Δημιουργώντας τα υποκλειδιά

1. Τοποθετούμε αρχικές τιμές στους πίνακες Ρ και στα τέσσερα S-boxes. Οι αρχικές τιμές αποτελούνται από ψηφία του δεκαεξαδικό σύστημα μέτρησης π.χ. P₁=0x243f6a88 P₂=0x85a308d3 P₃=0x13198a2e P₄=0x03707344
2. XOR P₁ με τα πρώτα 32 bit του κλειδιού, XOR P₂ με τα υπόλοιπα 32 bit του κλειδιού και επαναλαμβάνεται αυτή η διαδικασία για όλα τα Ρ.
3. Κωδικοποίησε όλες τις μηδενικές συμβολοσειρές με τον αλγόριθμο του blowfish κάνοντας χρήση όλων των υποκλείδιων όπου δημιουργήσαμε στα βήματα (1) και (2).
4. Αντικατάστησε τα $P_{1}$ και $P_{2}$ με το αποτέλεσμα του βήματος (3).
5. Κωδικοποίησε το αποτέλεσμα του βήματος (3) κάνοντας χρήση του αλγορίθμου του blowfish με τα τροποποιημένα κλειδιά.
6. Αντικατάστησε τα $P_{3}$ και $P_{4}$ με το αποτέλεσμα του βήματος (5)
7. Συνέχισε αυτήν την διαδικασία αντικατάστασης των πινάκων Ρ και των τεσσάρων S-boxes με έξοδο το συνεχώς μεταβαλλόμενο αλγόριθμο του blowfish

Συνολικά χρειάζονται 521 επαναλήψεις για να δημιουργηθούν όλα τα κλειδιά.

Κρυπτογράφηση-αποκρυπτογράφηση

Ψευδοκώδικας

ΕΙΣΟΔΟΣ: 64 bit δεδομένων x
Χώρισε το x στην μέση δηλαδή σε XL και XR 
Για i=1 μέχρι 16 επανέλαβε:
	XL = XL XOR Pi 
	XR = F(XL) XOR XR
	Αντιμετάθεσε XL και XR
Αντιμετάθεσε XL και XR (ακυρώνει την τελευταία αντιμετάθεση)
XR = XR XOR P17
XL = XL XOR P18
Ξαναένωσε τα XL και XR

Συνάρτηση F

Η συνάρτηση F χωρίζει το XL, όπου δέχεται σαν είσοδο σε τέσσερα τμήματα των οχτώ-bit τα a,b,c,d. Δηλαδή γίνεται αυτή η ακόλουθη πράξη:
F(XL)=(S(1,a)+S(2,b) mod 232 XOR S(3,c))+ S(4,d) mod 232

Η αποκρυπτογράφηση είναι η ίδια ακριβώς με την διαφορά πως τα $P_{1},P_{2},...,P_{18}$ χρησιμοποιούνται με την αντίστροφη σειρά.

Mini blowfish

Οι mini blowfish χρησιμοποιούνται για εκπαιδευτικούς σκοπούς και για κρυπτοάναλυση. Η διαδικασία υλοποίησης είναι ίδια με την διάφορα στις τιμές Ο blowfish-32 έχει 32 bit μεγέθους μπλοκ και υποκλειδιά μεγέθους 16 bit κάθε S-box έχει 16 bit εισόδους. Ο blowfish-16 έχει 16 bit μεγέθους μπλοκ και υποκλειδιά μεγέθους 8 bit κάθε S-box έχει 4 bit εισόδους.

Σχετικά με την σχεδίαση

Ακολουθούν πληροφορίες σχετικά με τις αποφάσεις όπου πάρθηκαν για σχεδίαση

• Η βασική φιλοσοφία του Blowfish είναι η δημιουργία ενός αλγορίθμου όπου είναι απλό στην κατανόηση αλλά και στην υλοποίηση.
• Τo δίκτυο Feistel όπου είναι το σώμα του Blowfish είναι σχεδιασμένο έτσι ώστε να είναι όσο το δυνατό ποίο απλό αλλά και να κρατά τις κρυπτογραφικές ιδιότητες όπου έχει η αρχική δομή. Αυτό επιτυγχάνεται με την χρήση μοναδικής XOR σε αντίθεση με το τετραπλό XOR όπου έχει ο Feistel.
• Η συνάρτηση F δίνει στον αλγόριθμο ο καλύτερο δυνατό avalanche effect για ένα δίκτυο Feistel κάθε bit στο αριστερό μισό επηρεάζει κάθε bit στο δεξιό μισό. Επιπροσθέτως από την στιγμή όπου κάθε bit του υποκλειδίου επηρεάζεται από κάθε Bit του κλειδιού. Ακόμη η συνάρτηση f μας δίνει το καλύτερο δυνατό φαινόμενο της χιονοστιβάδας στον τρίτο γύρο και μετά από κάθε δύο γύρους.
• Έγινε χρήση τεσσάρων S-box αντί ενός S-box κυρίως για να αποφευχθεί η συμμετρία στο κωδικοποιημένο μήνυμα. Επίσης θα μπορούσε να γίνει χρήση ένα μεγάλο S-box το οποίο θα είχε τις δυνατότητες των τεσσάρων αλλά τότε θα είχαμε ένα αργό σύστημα και θα ήταν ποιο δύσκολο στην υλοποίησή του.
• Στην αλγοριθμική σχεδίαση υπάρχουν δυο βασικοί τρόποι για να βεβαιωθείς ότι το κλειδί σου είναι αρκετά μεγάλο για να έχεις ένα σοβαρό επίπεδο ακρίβειας. Ό ένας ο τρόπος είναι να σχεδιάσεις ολόκληρο τον αλγόριθμο έτσι ώστε να διατηρεί ολόκληρη την εντροπία με αποτέλεσμα ο μοναδικός τρόπος για να κάνεις κρυπτοανάλυση στον αλγόριθμο να είναι με ωμή βία. Ο άλλος τρόπος είναι να σχεδιάσεις τον αλγόριθμο τέτοιο ώστε το κλειδί να είναι με τόσα πολλά bits έτσι επιθέσεις όπου μειώνουν την αποτελεσματικότητα του μήκους του κλειδιού να είναι άσχετες.
• Η διαδικασία για την δημιουργία των υποκλειδιών έχει ως στόχο να διατηρήσει την εντροπία του κλειδιού και να την διαμείνει σε ολόκληρο το υποκλειδί.
• Στην διαδικασία για την δημιουργία του υποκλειδίου τα υποκλειδιά αλλάζουν ελάχιστα από τα υπόλοιπα. Αυτό γίνεται για να προστατεύει ενάντια σε οποιαδήποτε επίθεση όπου έχει ως στόχο να χτυπήσει την διαδικασία δημιουργίας των υποκλειδίων.

Πηγές

1. Bruce Schneier. «Description of a New Variable-Length Key, 64-Bit Block Cipher (Blowfish)».