Blowfish

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

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

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

Σε Bulk κρυπτογραφία. Ο αλγόριθμος πρέπει να είναι αποδοτικός όταν κωδικοποιεί αρχεία ή όταν κωδικοποιεί μια συνεχή ροή δεδομένων.

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

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

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

Συσκευές

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

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

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

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

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

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

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

O blowfish είναι ένας αλγόριθμος κρυπτογραφίας τμήματος όπου χρησιμοποιεί 64 bit κρυπτογράφημα. Αποτελείται από δύο τμήματα το πρώτο είναι η επέκταση του κλειδιού και το δεύτερο είναι το κομμάτι όπου γίνεται η κρυπτογράφηση. Η επέκταση του κλειδιού μετατρέπει ένα κλειδί μέγιστου μεγέθους 448 bits σε πολλά υποκλειδιά συνολικού μεγέθους 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₁ και P₂ με το αποτέλεσμα του βήματος (3).
5. Κωδικοποίησε το αποτέλεσμα του βήματος (3) κάνοντας χρήση του αλγορίθμου του blowfish με τα τροποποιημένα κλειδιά.
6. Αντικατάστησε τα Ρ_3 και Ρ_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

Η αποκρυπτογράφηση είναι η ίδια ακριβώς με την διαφορά πως τα Ρ_1,Ρ_2,…,Ρ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)».