Anakoinw8ike o diadoxos tou DES: RIJNDAEL

Sun Oct 8 19:26:05 EEST 2000

On Thu, Oct 05, 2000 at 03:49:25PM +0100, Vasilis Vasaitis wrote:
> On Tue, Oct 03, 2000 at 02:46:27PM +0000, S.Xenitellis at rhbnc.ac.uk wrote:
> > 
> > O diadoxos tou DES anakoinw8ike xtes, deftera 2 Oktovriou
> > apo to NIST (Epitropi Erevnwn tvn HPA), gia xrisi
> > apo kybernitikes ypiresies kai tritous.
> 
>   Μήπως μπορεί κάποιος που ξέρει περισσότερα για κρυπτογραφία (nmav?) να μας
> πει τη γνώμη του για αυτήν την επιλογή; Για παράδειγμα, βλέπω στην παραπάνω
> σελίδα ότι αρκετοί αλγόριθμοι πέρασαν στον δεύτερο γύρω: MARS, RC6,
> RijnDael, Serpent, Twofish. Πώς συγκρίνονται μεταξύ τους; Ήταν "καλή"
> επιλογή; Αυτά...

Όπως είναι γνωστό ο DES θεωρείται πλέον unsecure, πρώτα από όλα εξαιτίας 
του ότι είναι vulnarable σε brute-force attack.  Ενδεικτικά αναφέρω ότι έχουν 
κατασκευαστεί μηχανές special-purposed για τον DES οι οποίες μπορούν μέσα σε 
διάστημα μερικών ωρών [0] να βρουν το key που έχει χρησιμοποιηθεί για το 
encryption, γεγονός που οφείλεται στο μήκος του -μόνο 56bit- που επιτρέπει 
2^56 συνδυασμούς.  

Οπότε, πριν 4 περίπου χρόνια ξεκίνησε η διαδικασία αντικατάστασης του DES από 
τον AES.  To NIST ανέλαβε την διεξαγωγή της, κάτω από συνθήκες πλήρους 
διαφάνειας [1].  Το key size που θα υποστηρίζει ο αλγόριθμος θα πρέπει να 
είναι 128, 192 και 256bit, γεγονός που συνεπάγεται ότι ακόμα και με μία
"cracker machine" παρομοίων δυνατοτήτων με την παραπάνω και key μήκους 128bit 
(δηλ. 2^128 possible keys) θα χρειαζόντουσαν τρισ-εκατομμύρια χρόνια για ένα 
επιτυχές brute-force attack [2].  

Από όλους τους διαγωνιζόμενους αλγόριθμους μετά τον πρώτο γύρο επιλέχθηκαν 
15 [3] και από αυτούς τον 2ο γύρο πέρασαν 5 αλγόριθμοι [4].  Φυσικά όλα αυτά 
δεν έγιναν αστραπιαία.  Για παράδειγμα από τον 1ο στον 2ο γύρο μεσολάβησε 
περίπου ένας χρόνος όπου κρυπταναλυτές προσπαθούσαν να επιτεθούν στους 
αλγόριθμους με όλες τις γνωστές και μη μεθόδους.  Τελικά επιλογή του NIST 
για AES αποτέλεσε, όπως είναι γνωστό, ο Rijndael [5] (προφέρεται "Reign Dahl").

Οι 5 αλγόριθμοι που πέρασαν στο 2nd Round θεωρούνται "εξίσου" ασφαλείς και
οποιοσδήποτε από αυτούς θα μπορούσε να είναι ο επιλεγμένος AES.  Το θέμα 
είναι πως το NIST είχε θέσει επιπλέον όρους πέρα από τα security issues.  
Αναφέρω ορισμένα από αυτά [6]: 
- Ο AES πρέπει να είναι αρκετά flexible ώστε να μπορεί χρησιμοποιηθεί 
  από επεξεργαστές 64, 32 και μέχρι 8bits που χρησιμοποιούνται στα smart 
  cards.  
- Το implementation του αλγόριθμου να μπορεί να γίνει τόσο σε software όσο 
  και σε hardware.  
- Ταχύτητα του αλγορίθμου: στην δημιουργία του key, encryption, decryption, 
  κλπ.  
- Άδεια χρήσης κατάλληλη για χρήση του AES παγκοσμίως χωρίς περιορισμούς.  

Μία πολύ πολύ περιληπτική και εντελώς επιφανειακή, χωρίς μαθηματικά, 
συναρτήσεις, πηγαίο κώδικα και άλλες λεπτομέρειες σύγκριση: [7]

Οι Rijndael και RC6 θεωρούνται οι απλούστεροι στο implementation τους 
γεγονός που οι περισσότεροι cryptanalysts θεωρούν bonus για το security 
ενός κρυπτογραφικού αλγόριθμου.  Επίσης, οι δύο τους είναι οι ταχύτεροι στο 
στο en(de)cryption με τον Rijndael να πλεονεκτεί στο ότι πέτυχε εξίσου καλά
αποτελέσματα στις διάφορες αρχιτεκτονικές που δοκιμάστηκε (ο RC6 είναι ο 
γρηγορότερος στις 32bit πλατφόρμες) και τον Twofish να ακολουθεί.  Στο key 
setup ταχύτερος είναι ο Rijndael, ο οποίος όμως υστερεί σε σχέση με τους 
άλλους στο ότι όσο μεγαλύτερο το key size που χρησιμοποιείται μειώνεται η 
ταχύτητα του en(de)cryption.  

Για περιβάλλοντα με περιορισμένα resources το προβάδισμα έχουν οι Twofish, 
Serpent με τον Rijndael να ακολουθεί κυρίως λόγω του μεινοκτήματος του να 
αυξάνει σε απαιτήσεις όταν γίνεται ταυτόχρονα encryption και decryption 
implementation.  Το τελευταίο αυτό χαρακτηριστικό έχουν οι MARS, RC6 και 
Twofish χάρη στην ομοιότητα των συναρτήσεων που χρησιμοποιούνται για 
encryption και decryption. Ακόμα, ικανότεροι για hardware implementation 
είναι οι Rijndael και Serpent.  Στην ικανότητα των αλγορίθμων για γρήγορη
εναλλαγή πολλών keys για διαφορετικές χρήσεις (key agility) (πχ. IPsec) 
ξεχωρίζουν οι Twofish, Serpent και Rijndael. Τέλος, ο Rijndael είναι 
πιθανότερο από τους υπόλοιπους να ωφελειθεί από level-instruction 
parallelism.

Γενικά στην κρυπτογραφία δεν μπορεί κανείς να πει με σιγουριά ότι ο Χ
αλγόριθμος είναι απολύτως secure [8], διότι ένα άλμα στα θεωρητικά μαθηματικά 
ή στην κρυπτανάλυση μπορεί να αλλάξει πολλά πράγματα.  Ομοίως, και μία
"ασύλληπτη" για εμάς πρόοδος στην τεχνολογία των υπολογιστικών μηχανών.  

Σημαντικό είναι το γεγονός ότι τα τελευταία χρόνια άριστοι κρυπταναλυτές 
ερευνούν για την παγκόσμια ακαδημαική κοινότητα και όχι για την NSA [9] όπως 
συνέβαινε παλαιότερα.  

[0] Για μια τέτοια μηχανή αξίας περίπου $1Μ λιγότερο από 3h.  Υπάρχει 
    και μία φήμη που θέλει την NSA να σπάει τον DES σε 3-15min!  
[1] Ο AES θα χρησιμοποιηθεί και από την κυβέρνηση των ΗΠΑ και τις 
    βιομηχανίες της, κίνητρο για καλή επιλογή του.  Εξάλλου ανεξάρτητοι 
    κρυπταναλυτές επιβλέπουν ή/και συμμετέχουν στην διαδικασία.  
[2] Πάντως, για symmetric encryption και key πάνω από 219bit, ο 
    θερμοδυναμικός νόμος δεν επιτρέπει brute-force attack για τους Η/Υ 
    κατασκευασμένους από υλικό. (!?)
[3] http://csrc.nist.gov/encryption/aes/round1/round1.htm
[4] http://csrc.nist.gov/encryption/aes/round2/r2algs.htm
[5] http://www.esat.kuleuven.ac.be/~rijmen/rijndael/
[6] http://csrc.nist.gov/encryption/aes/pre-round1/aes_9709.htm
[7] http://csrc.nist.gov/encryption/aes/round2/r2report.pdf
    http://www.counterpane.com/aes-performance.html
    http://www.counterpane.com/aes-entries.html
[8] Εκτός από τα one-time pads.  
[9] http://www.nsa.gov

ΥΓ. Όποιος έφτασε μέχρι εδώ, του αφιερώνω το Paranoid των Black Sabbath :-)

--
linux-greek-users mailing list -- http://lists.hellug.gr