Κρυπτογραφικοί Αλγόριθμοι Ροής
Στην κρυπτογραφία, ένας κρυπτογράφος ροής είναι ένας κρυπτογράφος συμμετρικού κλειδιού όπου τα bits του απλού κειμένου συνδυάζονται με μια ψευδοτυχαία ροή κρυπτογραφικών bit (keystream) χρησιμοποιώντας μια πράξη αποκλειστικής ή (xor). Σε μια κρυπτογράφηση ροής τα ψηφία του απλού κειμένου κρυπτογραφούνται ένα προς ένα και ο μετασχηματισμός των διαδοχικών ψηφίων μεταβάλλεται κατά τη διάρκεια της κατάστασης κρυπτογράφησης. Μια εναλλακτική ονομασία είναι κρυπτογράφηση κατάστασης, καθώς η κρυπτογράφηση κάθε ψηφίου εξαρτάται από την τρέχουσα κατάσταση. Στην πράξη, τα ψηφία είναι συνήθως μεμονωμένα bits ή bytes.
Οι κρυπτογραφήσεις ροής αντιπροσωπεύουν μια διαφορετική προσέγγιση στη συμμετρική κρυπτογράφηση από τις κρυπτογραφήσεις μπλοκ. Οι block ciphers λειτουργούν σε μεγάλα μπλοκ σταθερού μήκους. Οι κρυπτογράφοι ροής συνήθως εκτελούνται με υψηλότερη ταχύτητα από τους κρυπτογράφους μπλοκ και έχουν χαμηλότερες απαιτήσεις υλικού. Ωστόσο, οι κρυπτογράφοι ροής μπορεί να είναι επιρρεπείς σε σοβαρά προβλήματα ασφάλειας αν χρησιμοποιηθούν εσφαλμένα- για παράδειγμα, ειδικότερα, η ίδια αρχική κατάσταση δεν πρέπει ποτέ να χρησιμοποιείται δύο φορές.
Ένας κρυπτογράφος ροής χρησιμοποιεί ένα πολύ μικρότερο και πιο βολικό κρυπτογραφικό κλειδί, για παράδειγμα κλειδιά 128 bit. Με βάση αυτό το κλειδί, παράγει ένα ψευδοτυχαίο keystream το οποίο μπορεί να συνδυαστεί με τα ψηφία του απλού κειμένου με παρόμοιο τρόπο όπως ο αλγόριθμος κρυπτογράφησης one-time pad. Ωστόσο, επειδή η ροή κλειδιών είναι ψευδοτυχαία και όχι πραγματικά τυχαία, δεν μπορεί να εφαρμοστεί η ασφάλεια που σχετίζεται με το one-time pad και είναι πολύ πιθανό ένας κρυπτογράφος ροής να είναι εντελώς ανασφαλής.
Η λειτουργία της γεννήτριας ροής κλειδιών στο A5/1, ένα κρυπτογράφημα ροής βασισμένο σε LFSR που χρησιμοποιείται για την κρυπτογράφηση συνομιλιών κινητών τηλεφώνων.
Τύποι κρυπτογράφησης ροής
Ένας κρυπτογράφος ροής παράγει διαδοχικά στοιχεία της ροής κλειδιών με βάση μια εσωτερική κατάσταση. Αυτή η κατάσταση ενημερώνεται με δύο τρόπους:
- Εάν η κατάσταση αλλάζει ανεξάρτητα από τα μηνύματα απλού κειμένου ή κρυπτοκειμένου, ο κρυπτογράφος ταξινομείται ως σύγχρονος κρυπτογράφος ροής.
- Εάν η κατάσταση ενημερώνεται με βάση προηγούμενες αλλαγές των ψηφίων του κρυπτοκειμένου, ο κρυπτογράφος ταξινομείται ως αυτοσυγχρονιζόμενος κρυπτογράφος ροής.
Σύγχρονοι κρυπτογράφοι ροής
Σε ένα σύγχρονο κρυπτογράφημα ροής δημιουργείται μια ροή ψευδοτυχαίων ψηφίων ανεξάρτητα από τα μηνύματα απλού κειμένου και κρυπτοκειμένου και στη συνέχεια συνδυάζεται με το απλό κείμενο (για κρυπτογράφηση) ή με το κρυπτοκείμενο (για αποκρυπτογράφηση). Στην πιο συνηθισμένη μορφή, χρησιμοποιούνται δυαδικά ψηφία(bits) και η ροή κλειδιών συνδυάζεται με το απλό κείμενο με τη χρήση της πράξης αποκλειστικής ή (XOR). Αυτό ονομάζεται δυαδική προσθετική κρυπτογράφηση ροής.
Σε ένα σύγχρονο κρυπτογράφημα ροής, ο αποστολέας και ο παραλήπτης πρέπει να είναι συγχρονισμένοι για να είναι επιτυχής η αποκρυπτογράφηση. Εάν προστεθούν ή αφαιρεθούν ψηφία από το μήνυμα κατά τη διάρκεια της μετάδοσης, ο συγχρονισμός χάνεται. Για να αποκατασταθεί ο συγχρονισμός, μπορούν να δοκιμαστούν συστηματικά διάφορες μετατοπίσεις για να επιτευχθεί η σωστή αποκρυπτογράφηση. Μια άλλη προσέγγιση είναι η σήμανση του κρυπτογραφημένου κειμένου με δείκτες σε τακτά σημεία της εξόδου.
Εάν, ωστόσο, ένα ψηφίο αλλοιωθεί κατά τη μετάδοση, αντί να προστεθεί ή να χαθεί, επηρεάζεται μόνο ένα ψηφίο στο απλό κείμενο και το σφάλμα δεν μεταδίδεται σε άλλα μέρη του μηνύματος. Αυτή η ιδιότητα είναι χρήσιμη όταν ο ρυθμός σφάλματος μετάδοσης είναι υψηλός- ωστόσο, καθιστά λιγότερο πιθανό να εντοπιστεί το σφάλμα χωρίς περαιτέρω μηχανισμούς. Επιπλέον, εξαιτίας αυτής της ιδιότητας, οι σύγχρονοι κρυπτογράφοι ροής είναι πολύ ευάλωτοι σε ενεργέςεπιθέσεις - εάν ένας επιτιθέμενος μπορεί να αλλάξει ένα ψηφίο στο κρυπτογράφημα, μπορεί να είναι σε θέση να κάνει προβλέψιμες αλλαγές στο αντίστοιχο bit του απλού κειμένου- για παράδειγμα, η αναστροφή ενός bit στο κρυπτογράφημα προκαλεί την αναστροφή(Toggled) του ίδιου bit στο απλό κείμενο.
Αυτοσυγχρονιζόμενοι κρυπτογράφοι ροής
Οι αυτοσυγχρονιζόμενοι κρυπτογράφοι ροής είναι μια άλλη τεχνική που χρησιμοποιεί μέρος των προηγούμενων Ν ψηφίων κρυπτοκειμένου για τον υπολογισμό της κλειδοροής. Τέτοια συστήματα είναι επίσης γνωστά ως ασύγχρονοι κρυπτογράφοι ροής ή αυτόματο κλειδί κρυπτοκειμένου (CTAK). Η ιδέα του αυτοσυγχρονισμού κατοχυρώθηκε με δίπλωμα ευρεσιτεχνίας το 1946 και έχει το πλεονέκτημα ότι ο δέκτης θα συγχρονιστεί αυτόματα με τη γεννήτρια του keystream μετά τη λήψη Ν ψηφίων κρυπτοκειμένου, γεγονός που καθιστά ευκολότερη την ανάκτηση αν πέσουν ή προστεθούν ψηφία στη ροή του μηνύματος. Τα μονοψήφια σφάλματα είναι περιορισμένα στην επίδρασή τους, επηρεάζοντας μόνο μέχρι Ν ψηφία καθαρού κειμένου. Είναι κάπως πιο δύσκολο να πραγματοποιηθούν ενεργές επιθέσεις σε αυτοσυγχρονιζόμενους κρυπτογράφους ροής παρά σε σύγχρονους αντίστοιχους.
Ένα παράδειγμα αυτοσυγχρονιζόμενου κρυπτογραφήματος ροής είναι ένα κρυπτογράφημα μπλοκ σε λειτουργία ανατροφοδότησης κρυπτογράφησης (CFB).
Κωδικοποιητές ροής βασισμένοι σε καταχωρητή μετατόπισης γραμμικής ανάδρασης
Τα δυαδικά κρυπτογραφήματα ροής κατασκευάζονται συχνά με τη χρήση καταχωρητών μετατόπισης γραμμικής ανάδρασης (LFSR), επειδή μπορούν να υλοποιηθούν εύκολα σε υλικό και να αναλυθούν γρήγορα μαθηματικά. Ωστόσο, η χρήση μόνο των LFSRs δεν επαρκεί για την παροχή καλής ασφάλειας. Έχουν σχεδιαστεί διάφορα συστήματα για την αύξηση της ασφάλειας των LFSRs.
Μη γραμμικές συναρτήσεις συνδυασμού
Επειδή τα LFSR είναι εγγενώς γραμμικά, μια τεχνική για την άρση της γραμμικότητας είναι η τροφοδότηση των εξόδων μιας ομάδας παράλληλων LFSR σε μια μη γραμμική συνάρτηση Boole για να σχηματιστεί μια γεννήτρια συνδυασμού. Διάφορες ιδιότητες μιας τέτοιας συνάρτησης συνδυασμού είναι σημαντικές για τη διασφάλιση της ασφάλειας του προκύπτοντος σχήματος, για παράδειγμα, για την αποφυγή επιθέσεων συσχέτισης.
Γεννήτριες ελεγχόμενες με ρολόι
Κανονικά τα LFSRs βηματίζονται τακτικά. Μια τεχνική για την εισαγωγή μη γραμμικότητας είναι να χρονίζεται το LFSR ακανόνιστα, ελεγχόμενο από την έξοδο ενός δεύτερου LFSR. Τέτοιες γεννήτριες είναι η γεννήτρια stop-and-go, η γεννήτρια εναλλασσόμενου βήματος και η γεννήτρια συρρίκνωσης.
Η γεννήτρια stop-and-go (Beth and Piper, 1984) αποτελείται από δύο LFSR. Το ένα LFSR χρονίζεται εάν η έξοδος του δεύτερου είναι "1", διαφορετικά επαναλαμβάνει την προηγούμενη έξοδό του. Αυτή η έξοδος συνδυάζεται στη συνέχεια (σε ορισμένες εκδόσεις) με την έξοδο ενός τρίτου LFSR που χρονίζεται με κανονικό ρυθμό.
Η γεννήτρια συρρίκνωσης χρησιμοποιεί μια διαφορετική τεχνική. Χρησιμοποιούνται δύο LFSR, και τα δύο χρονισμένα τακτικά με τον ακόλουθο τρόπο:
- Εάν η έξοδος του πρώτου LFSR είναι "1", η έξοδος του δεύτερου LFSR γίνεται η έξοδος της γεννήτριας.
- Εάν η έξοδος του πρώτου LFSR "0", η έξοδος του δεύτερου απορρίπτεται και κανένα bit δεν εξάγεται από τη γεννήτρια.
Αυτή η τεχνική πάσχει από επιθέσεις χρονισμού στη δεύτερη γεννήτρια, καθώς η ταχύτητα της εξόδου μεταβάλλεται με τρόπο που εξαρτάται από την κατάσταση της δεύτερης γεννήτριας. Αυτό μπορεί να βελτιωθεί με την προσωρινή αποθήκευση της εξόδου.
Γεννήτρια φίλτρων
Μια άλλη προσέγγιση για τη βελτίωση της ασφάλειας ενός LFSR είναι να περάσει ολόκληρη η κατάσταση ενός μεμονωμένου LFSR σε μια μη γραμμική συνάρτηση φιλτραρίσματος.
Άλλα σχέδια
Αντί για μια γραμμική συσκευή οδήγησης, μπορεί να χρησιμοποιηθεί μια μη γραμμική συνάρτηση ενημέρωσης. Για παράδειγμα, οι Klimov και Shamir πρότειναν τριγωνικές συναρτήσεις (T-Functions) με έναν μόνο κύκλο σε n bit words.
Ασφάλεια
Για να είναι ασφαλές, η περίοδος της ροής κλειδιών (ο αριθμός των ψηφίων που εξάγονται πριν η ροή επαναληφθεί) πρέπει να είναι αρκετά μεγάλη. Εάν η ακολουθία επαναλαμβάνεται, τότε τα επικαλυπτόμενα κρυπτογραφήματα μπορούν να ευθυγραμμιστούν μεταξύ τους "σε βάθος" και υπάρχουν τεχνικές που επιτρέπουν την εξαγωγή του απλού κειμένου από κρυπτογραφήματα που παράγονται με αυτές τις μεθόδους.
Χρήση
Οι κρυπτογραφήσεις ροής χρησιμοποιούνται συχνά σε εφαρμογές όπου το απλό κείμενο είναι σε ποσότητες μη γνωστού μήκους, όπως στις ασφαλείς ασύρματες συνδέσεις. Εάν ένας κρυπτογράφος μπλοκ χρησιμοποιούνταν σε αυτού του είδους τις εφαρμογές, ο σχεδιαστής θα έπρεπε να επιλέξει είτε την αποδοτικότητα μετάδοσης είτε την πολυπλοκότητα υλοποίησης, δεδομένου ότι οι κρυπτογράφοι μπλοκ δεν μπορούν να εργαστούν άμεσα σε μπλοκ μικρότερα από το μέγεθος του μπλοκ τους. Για παράδειγμα, εάν ένας κρυπτογράφος μπλοκ 128 bit λάβει ξεχωριστές ριπές απλού κειμένου 32 bit, τα τρία τέταρτα των μεταδιδόμενων δεδομένων χρειάζονται συμπλήρωση. Οι κρυπτογράφηση μπλοκ πρέπει να χρησιμοποιείται σε λειτουργία κλοπής κρυπτοκειμένου ή τερματισμού υπολειπόμενου μπλοκ για να αποφευχθεί η συμπλήρωση, ενώ οι κρυπτογραφήσεις ροής εξαλείφουν αυτό το ζήτημα λειτουργώντας στη μικρότερη μεταδιδόμενη μονάδα (συνήθως bytes).
Ένα άλλο πλεονέκτημα των κρυπτογραφήσεων ροής στη στρατιωτική κρυπτογραφία είναι ότι η ροή κρυπτογράφησης μπορεί να παραχθεί από μια συσκευή κρυπτογράφησης που υπόκειται σε αυστηρά μέτρα ασφαλείας και στη συνέχεια να τροφοδοτηθεί σε άλλες συσκευές, π.χ. σε μια ραδιοφωνική συσκευή, οι οποίες θα εκτελέσουν την πράξη xor ως μέρος της λειτουργίας τους. Η άλλη συσκευή μπορεί να σχεδιαστεί για χρήση σε λιγότερο ασφαλή περιβάλλοντα.
Το RC4 είναι το πιο ευρέως χρησιμοποιούμενο κρυπτογράφημα ροής στο λογισμικό: A5/1, A5/2, Chameleon, FISH, Helix, ISAAC, MUGI, Panama, Phelix, Pike, SEAL, SOBER, SOBER-128 και WAKE.
Το RC4 είναι ένα από τα πιο ευρέως χρησιμοποιούμενα σχέδια κρυπτογράφησης ροής.
Σύγκριση των κρυπτών ροής
| StreamCipher | CreationDate | Ταχύτητα | (bits) | Επίθεση | |||
| Αποτελεσματικό | Διάνυσμα αρχικοποίησης | InternalState | Γνωστότερος | Υπολογιστική πολυπλοκότητα | |||
| A5/1 | 1989 | Φωνή (Wphone) | 54 | 114 | 64 | Ενεργό KPA Ή | ~2 δευτερόλεπτα OR239.91 |
| A5/2 | 1989 | Φωνή (Wphone) | 54 | 114 | 64? | Ενεργό | 4,6 χιλιοστά του δευτερολέπτου |
| ΨΆΡΙΑ | 1993 | Αρκετά γρήγορο (Wsoft) | Τεράστιο | Επίθεση γνωστού κειμένου | 211 | ||
| Δημητριακά | Πριν από το 2004 | Γρήγορη | 80 | 64 | 160 | Κλειδί-Αποσύνδεση | 243 |
| HC-256 | Πριν από το 2004 | 4 (WP4) | 256 | 256 | 65536 | ||
| ISAAC | 1996 | 2.375 (W64-bit) | 8-8288συνήθως | N/A | 8288 | (2006) Πρώτος γύροςΑδύναμη-Εσωτερική-Κράτος-απομάκρυνση | 4.67×101240 (2001) |
| MUGI | 1998-2002 | 128 | 128 | 1216 | N/A (2002) | ~282 | |
| PANAMA | 1998 | 2 | 256 | 128? | 1216? | Hash Collisions (2001) | 282 |
| Phelix | Πριν από το 2004 | έως 8 (Wx86) | 256 + 128-bit Nonce | 128? | Διαφορικό (2006) | 237 | |
| Pike | 1994 | 0,9 x FISH (Wsoft) | Τεράστιο | N/A (2004) | N/A (2004) | ||
| Py | Πριν από το 2004 | 2.6 | 8-2048? | 64 | 8320 | Κρυπταναλυτική θεωρία (2006) | 275 |
| Κουνέλι | 2003-Φεβρουάριος | 3,7 (WP3)-9,7 (WARM7) | 128 | 64 | 512 | N/A (2006) | N/A (2006) |
| 1987 | Εντυπωσιακό | 8-2048συνήθως | 8 | 2064 | Shamir Initial-Bytes Key-Derivation OR KPA | 213 OR 233 | |
| Salsa20 | Πριν από το 2004 | 4,24 (WG4) -11 | 128 + 64-bit Nonce | 512 | 512 + 384 (κλειδί+IV+δείκτης) | Διαφορικό (2005) | N/A (2005) |
| Scream | 2002 | 4 - 5 (Wsoft) | 128 + 128-bit Nonce | 32? | 64-bit round function | ||
| SEAL | 1997 | Πολύ γρήγορη (W32-bit) | 32? | ||||
| SNOW | Πριν από το 2003 | Πολύ καλό (W32-bit) | 128 Ή 256 | 32 | |||
| SOBER-128 | 2003 | έως 128 | Μήνυμα Forge | 2−6 | |||
| SOSEMANUK | Πριν από το 2004 | Πολύ καλό (W32-bit) | 128 | 128 | |||
| Trivium | Πριν από το 2004 | 4 (Wx86) - 8 (WLG) | 80 | 80 | 288 | Επίθεση ωμής βίας (2006) | 2135 |
| Turing | 2000-2003 | 5.5 (Wx86) | 160 | ||||
| VEST | 2005 | 42 (WASIC) -64 (WFPGA) | Μεταβλητήσυνήθως | Μεταβλητήσυνήθως | 256 - 800 | N/A (2006) | N/A (2006) |
| WAKE | 1993 | Γρήγορη | 8192 | CPA & CCA | Ευάλωτο | ||
| StreamCipher | CreationDate | Ταχύτητα | (bits) | Επίθεση | |||
| Αποτελεσματικό | Διάνυσμα αρχικοποίησης | InternalState | Γνωστότερος | Υπολογιστική πολυπλοκότητα | |||
Σχετικές σελίδες
- eSTREAM
Ερωτήσεις και απαντήσεις
Q: Τι είναι ο κρυπτογράφος ροής;
A: Ένας κρυπτογράφος ροής είναι ένας κρυπτογράφος συμμετρικού κλειδιού όπου τα bits του απλού κειμένου συνδυάζονται με μια ψευδοτυχαία ροή κρυπτογραφημένων bit (keystream) χρησιμοποιώντας μια πράξη αποκλειστικού ή (xor).
Ε: Πώς διαφέρει από τους κρυπτογράφους μπλοκ;
Α: Οι κρυπτογράφοι ροής συνήθως εκτελούνται με υψηλότερη ταχύτητα από τους κρυπτογράφους μπλοκ και έχουν χαμηλότερες απαιτήσεις υλικού. Οι block ciphers λειτουργούν σε μεγάλα μπλοκ σταθερού μήκους, ενώ οι stream ciphers κρυπτογραφούν ψηφία ένα προς ένα και ο μετασχηματισμός των διαδοχικών ψηφίων μεταβάλλεται κατά τη διάρκεια της κατάστασης κρυπτογράφησης.
Ερ: Τι είδους κλειδιά χρησιμοποιεί;
Α: Οι κρυπτογράφοι ροής χρησιμοποιούν πολύ μικρότερα και πιο βολικά κρυπτογραφικά κλειδιά, για παράδειγμα κλειδιά 128 bit.
Ερ: Πώς παράγει τη ροή κλειδιών;
Α: Το keystream παράγεται με βάση το κρυπτογραφικό κλειδί που χρησιμοποιείται, με παρόμοιο τρόπο με τον αλγόριθμο κρυπτογράφησης one-time pad. Ωστόσο, επειδή το keystream είναι ψευδοτυχαίο και όχι πραγματικά τυχαίο, δεν μπορεί να εφαρμοστεί η ασφάλεια που σχετίζεται με το one-time pad.
Ερ: Γιατί δεν πρέπει ποτέ να χρησιμοποιείτε την ίδια αρχική κατάσταση δύο φορές;
Α: Η χρήση της ίδιας κατάστασης εκκίνησης δύο φορές μπορεί να οδηγήσει σε σοβαρά προβλήματα ασφαλείας, καθώς διευκολύνει τους επιτιθέμενους να αποκρυπτογραφήσουν δεδομένα χωρίς να γνωρίζουν ή να έχουν πρόσβαση στο κρυπτογραφικό σας κλειδί.
Ερ: Υπάρχει κάποιος κίνδυνος που συνδέεται με τη χρήση κρυπτογράφησης ροής;
Α: Ναι, αν χρησιμοποιηθούν εσφαλμένα ή χωρίς τη λήψη των κατάλληλων προφυλάξεων, τότε υπάρχει κίνδυνος που συνδέεται με τη χρήση των κρυπτογράφων ροής, καθώς μπορεί να είναι εντελώς ανασφαλείς αν δεν αντιμετωπιστούν σωστά.
