Data Encryption Standard

Ιστορικά

  Γενικά

Ο DES είναι ένας κρυπταλγόριθμος που έχει επιλεγεί ως επίσημο Ομοσπονδιακό Πρότυπο Επεξεργασίας Πληροφοριών (Federal Information Processing Standard - FIPS) για τις Ηνωμένες Πολιτείες το 1976. Ο DES στη συνέχεια, αρχίζει να χρησιμοποιείται διεθνώς. Ο αλγόριθμος αρχικά ήταν αμφισβητούμενος, με απόρρητα στοιχεία σχεδιασμού, ένα σχετικά μικρό μήκος κλειδιού. Υπήρχαν υποψίες πως η δημιουργία του DES επίσης αποσκοπούσε σε backdoor (κερκόπορτα) της αντιπροσωπίας της Υπηρεσίας Εθνικής Ασφάλειας (NSA) των Ηνωμένων Πολιτειών. Ο DES ήρθε στην επιφάνεια κάτω από την έντονη ακαδημαϊκή διερεύνηση και παρακίνησε στη σύγχρονη κατανόηση των block ciphers (κρυπταλγόριθμοι συμμετρικού κλειδιού) και στην κρυπτανάλυσή τους.

Ο DES, πλέον, θεωρείται ανασφαλής για πολλές εφαρμογές. Αυτό οφείλεται κυρίως στο μικρό μέγεθος του κλειδιού του που είναι 56-bit. Τον Ιανουάριο του 1999, οι εταιρείες distributed.net και η Electronic Frontier Foundation κατόπιν συνεργασίας “έσπασαν” δημοσίως ένα κλειδί του DES σε 22 ώρες και 15 λεπτά. Υπάρχουν επίσης ορισμένα αναλυτικά αποτελέσματα που αναπαριστούν θεωρητικές αδυναμίες στον κρυπταλγόριθμο, αν και είναι ανέφικτο να τοποθετηθούν στην πράξη. Θεωρείται πως ο αλγόριθμος είναι πρακτικά ασφαλής υπό τη μορφή του τριπλού DES (triple DES), αν και υπάρχουν θεωρητικές επιθέσεις. Τα τελευταία χρόνια, ο κρυπταλγόριθμος DES έχει εκτοπιστεί από τα Προηγμένα Πρότυπα Κρυπτογράφησης (Advanced Encryption Standard - AES).

Σε κάποια τεκμηρίωση, μια διάκριση γίνεται μεταξύ του DES ως πρότυπο, και του αλγορίθμου, ο οποίος αναφέρεται ως αλγόριθμος κρυπτογράφησης στοιχείων (Data Encryption Algorithm – DEA).

Η προέλευση του DES βρίσκεται στις αρχές της δεκαετίας του 1970. Το 1972, μετά την ολοκλήρωση μελέτης για την ασφάλεια των υπολογιστών της κυβέρνησης, το σώμα προτύπων των Η.Π.Α., γνωστό ως NBS (National Bureau of Standards) – που τώρα ονομάζεται NIST (National Institute of Standards and Technology) - επισήμανε την ανάγκη για ένα πρότυπο κυβερνήσεων που θα κρυπτογραφεί μη απόρρητες, ευαίσθητες πληροφορίες. Κατά συνέπεια, στις 15 Μαΐου του 1973, μετά από διαβούλευση με την NSA, η NBS κάνει προτάσεις για έναν κρυπταλγόριθμο που θα ανταποκρίνεται στα κριτήρια αυστηρού σχεδιασμού. Καμία από τις υποβολές, εντούτοις, δεν αποδείχθηκε κατάλληλη. Ένα δεύτερο αίτημα εκδόθηκε στις 27 Αυγούστου του 1974. Αυτή τη φορά, η IBM υπέβαλε έναν “υποψήφιο” που κρίθηκε αποδεκτός, ήταν ένας κρυπταλγόριθμος που αναπτύχθηκε κατά τη διάρκεια της περιόδου 1973-1974 βασισμένος σε έναν προηγούμενο αλγόριθμο. Ήταν ο κρυπταλγόριθμος Lucifer τον οποίο δημιούργησε ο Horst Feistel. Η ομάδα στην ΙΒΜ εξελίχθηκε στον σχεδιασμό και την ανάλυση κρυπταλγόριθμων με τη βοήθεια των Feistel, Walter Tuchman, Don Coppersmith, Alan Konheim, Carl Meyer, Mike Matyas, Roy Adler, Edna Grossman, Bill Notz, Lynn Smith και τον Bryart Tuckerman.

  Η ανάμειξη της NSA στον σχεδιασμό

Στις 17 Μαρτίου του 1975, ο προτεινόμενος DES δημοσιεύθηκε στον ομοσπονδιακό κατάλογο (Federal Register). Ζητήθηκαν δημόσια σχόλια και στο έτος που ακολούθησε, δύο ανοικτά εργαστήρια κλήθηκαν για να συζητήσουν τα προτεινόμενα πρότυπα. Υπήρξε κάποια κριτική από διάφορα μέλη, εκ των οποίων ήταν και οι πρωτοπόροι στην κρυπτογραφία δημοσίου κλειδιού Martin Hellman και Whitfield Diffie, που αναφέρουν ένα μικρότερο μήκος κλειδιού και τα μυστήρια "S-boxes” ως στοιχεία της ανάρμοστης παρέμβασης από την NSA. Η υποψία ήταν ότι ο αλγόριθμος ήταν αποδυναμωμένος συγκεκαλυμμένα από την Αντιπροσωπεία Νοημοσύνης (Intelligence Agency) έτσι ώστε παραμόνον αυτοί να μπορούν εύκολα να διαβάσουν τα κρυπτογραφημένα μηνύματα. Ο Alan Konheim (ένας από τους σχεδιαστές του DES) ανέφερε στα σχόλιά του: "Στείλαμε τα s-boxes στην Ουάσιγκτον. Επέστρεψαν και ήταν όλα διαφορετικά." Η Επίλεκτη Επιτροπή Συγκλήτου Νοημοσύνης των Ηνωμένων Πολιτειών (United States Senate Select Committee on Intelligence) αναθεώρησε τις ενέργειες της NSA ώστε να καθορίσει εάν υπήρξε οποιαδήποτε ανάρμοστη συμμετοχή. Στην αταξινόμητη περίληψη των συμπερασμάτων τους, που δημοσιεύθηκε το 1978, η Επιτροπή έγραψε:

"Στην ανάπτυξη του DES, η NSA έπεισε την IBM ότι ένα μειωμένο μήκος κλειδιού ήταν ικανοποιητικό. Έμμεσα βοηθημένη στην ανάπτυξη των S-box δομών και πιστοποιημένα ότι ο τελικός DES αλγόριθμος ήταν το καλύτερο της γνώσης τους, απαλλαγμένο από οποιαδήποτε στατιστική ή μαθηματική αδυναμία.”

Εν τούτοις, η επιτροπή ανακάλυψε και ανέφερε επίσης ότι:

"Η NSA δεν πείραξε το σχέδιο του αλγορίθμου από καμιά άποψη. Η ΙΒΜ εφηύρε και σχεδίασε τον αλγόριθμο, έλαβε όλες τις σχετικές αποφάσεις αναγνωρίζοντας την αξία του αλγόριθμου και συνέπεσε ότι η συμφωνία σχετικά με το μέγεθος του κλειδιού ήταν περισσότερο από επαρκής για όλες τις εμπορικές εφαρμογές για τις οποίες προοριζόταν ο DES." Ένα άλλο μέλος της ομάδας DES, ο Walter Tuchman, αναφέρεται πως είπε: "Αναπτύξαμε τον αλγόριθμο DES εξ' ολοκλήρου μέσα στην ΙΒΜ χρησιμοποιώντας IBMers. Η NSA δεν δικτύωσε ούτε ένα καλώδιο!"

Ορισμένες από τις υποψίες σχετικά με τις κρυφές αδυναμίες στα S-boxes είχαν εξαληφθεί το 1990, με την ανεξάρτητη ανακάλυψη και την ανοικτή δημοσίευση της Διαφορικής Κρυπτανάλυσης από τους Eli Biham και Adi Shamir, είναι μια γενική μέθοδος για το σπάσιμο των block chiphers. Τα S-boxes του DES ήταν πολύ πιο ανθεκτικά στην επίθεση απ' ό,τι αν είχαν επιλεγεί τυχαία, γεγονός που υποδηλώνει έντονα ότι η IBM γνώριζε για την τεχνική που εφαρμόζονταν πίσω στη δεκαετία του 1970. Αυτή ήταν πράγματι η υπόθεση, το 1994, ο Don Coppersmith δημοσίευσε τον αυθεντικό σχεδιασμό των κριτηρίων για τα S-boxes. Σύμφωνα με τον Steven Levi, οι ερευνητές της IBM Watson ανακάλυψαν διαφορικές κρυπταναλυτικές επιθέσεις το 1974 και ζητήθηκε από την NSA να κρατήσει την τεχνική μυστική. Ο Coppersmith εξηγεί την απόρρητη απόφαση της ΙΒΜ λέγοντας πως:

“Αυτό συνέβη επειδή η Διαφορική κρυπτανάλυση μπορεί να αποτελέσει ένα πολύ ισχυρό εργαλείο, που μπορεί να χρησιμοποιηθεί εναντίον πολλών συστημάτων-σχημάτων και υπήρχε ανησυχία ότι τέτοιες πληροφορίες στο δημόσιο τομέα θα μπορούσαν να επηρεάσουν δυσμενώς την εθνική ασφάλεια ". 

Ο Levy ανέφερε στον Walter Tuchman:

"Μας ζητήθηκε να σφραγίσουν όλα τα εμπιστευτικά μας έγγραφα... Πρέπει όντως να βάλουμε έναν αριθμό για κάθε ένα έγγραφο και να τα κλειδώσουμε σε χρηματοκιβώτια, επειδή θεωρήθηκαν απόρρητα έγγραφα της Αμερικανικής κυβέρνησης. Μου είπαν να το κάνω και έτσι το έκανα".

Ο Shamir σχολίασε πως σε αντίθεση με το τι πιστεύουν μερικοί άνθρωποι, δεν υπάρχουν ενδείξεις χειραγώγησης του DES, έτσι ώστε ο βασικός σχεδιασμός να εξασθενήσει. Η άλλη κριτική - ότι το μήκος του κλειδιού ήταν πολύ μικρό - ενισχύεται από το γεγονός ότι η αιτιολογία που δόθηκε από την NSA για τη μείωση του μήκους του κλειδιού από τα 64 bits στα 56 bits ήταν ότι τα υπόλοιπα 8 bits θα μπορούσαν να χρησιμεύσουν ως parity bits, πράγμα που έμοιαζε κάπως αληθοφανές. Ήταν ευρέως πιστευτό ότι η απόφαση της NSA τροποποιήθηκε λόγω της πιθανότητας να είναι σε θέση (η NSA) να κάνει επιτυχείς επιθέσεις τύπου brute force σε ένα κλειδί της τάξης των 56 bits αρκετά χρόνια πριν από τον υπόλοιπο κόσμο.

  Ο αλγόριθμος DES ως πρότυπο

Παρά τις επικρίσεις, ο DES εγκρίθηκε ως ένα ομοσπονδιακό πρότυπο, το Νοέμβριο του 1976 και δημοσιεύθηκε στις 15 Ιανουαρίου του 1977 ως FIPS PUB 46 και η χρήση του ήταν επιτρεπτή σε όλα τα μη απόρρητα δεδομένα. Στη συνέχεια, επιβεβαιώθηκε ως το πρότυπο το1983, το1988 (αναθεωρήθηκε ως FIPS-46-1), το 1993 (ως FIPS-46-2) και πάλι το 1999 (ως FIPS-46-3). Ο τελευταίος ορισμός ήταν ο Triple DES. Στις 26 Μαΐου του 2002, ο DES τελικά εκτοπίστηκε από τον Advanced Encryption Standard (AES) κατόπιν δημόσιου διαγωνισμού. Στις 19 Μαΐου του 2005, ο FIPS 46-3 είχε επισήμως αποσυρθεί, αλλά το Εθνικό Ινστιτούτο Προτύπων και Τεχνολογίας (National Institute of Standards and Technology - NIST) ενέκρινε τον Triple DES στο έτος 2003 για τις ευαίσθητες πληροφορίες της κυβέρνησης. Μια άλλη θεωρητική επίθεση, η γραμμική κρυπτανάλυση δημοσιεύθηκε το 1994, αλλά ήταν μια επίθεση brute force το 1998 που αναπαράστησε/απέδειξε ότι μπορεί κάποιος θα μπορούσε να επιτεθεί στον DES πολύ πρακτικά και τονίστηκε η ανάγκη για αντικατάσταση του αλγόριθμου. Αυτές και άλλες μέθοδοι κρυπτανάλυσης εξετάζονται λεπτομερώς. Η εισαγωγή του DES θεωρείται ότι ήταν ένας καταλύτης για την ακαδημαϊκή μελέτη της κρυπτογραφίας, ιδιαίτερα των μεθόδων για να “σπάνε” block κρυπταλγόριθμους, σύμ-φωνα με μια αναδρομή στο NIST για τον DES.

Ο DES, μπορεί να ειπωθεί, ότι το "αρχικό άλμα" του ξεπέρασε τις στρατιωτικές μελέτες και την ανάπτυξη των αλγορίθμων κρυπτογράφησης. Στη δεκαετία του 1970 υπήρχαν πολύ λίγοι κρυπτογράφοι, εκτός εκείνων των στρατιωτικών ή των μυστικών οργανώσεων και ελάχιστη ακαδημαϊκή μελέτη της κρυπτογραφίας. Υπάρχουν τώρα πολλοί δραστικοί ακαδημαϊκοί κρυπτολόγοι και μαθηματικά τμήματα με ισχυρά προγράμματα στην κρυπτογραφία και την ασφάλεια των πληροφοριών και των εμπορικών εταιρειών και συμβούλων. Μια γενιά κρυπταναλυτών έχει αναλύσει εξονυχιστικά τον αλγόριθμο DES προσπαθώντας να τον “σπάσουν”. Ανέφεραν πως ο DES έκανε περισσότερα για να γαλβανίσει τον τομέα της κρυπτανάλυσης από οτιδήποτε άλλο και έτσι υπήρχε ένας αλγόριθμος για τη μελέτη. Ένα εκπληκτικό μερίδιο της ανοιχτής λογοτεχνίας στην κρυπτογραφία κατά τη δεκαετία του 1970 και του 1980 ασχολήθηκε με τον DES και ο DES είναι το πρότυπο ενάντια σε όλους τους αλγόριθμους συμμετρικού κλειδιού μετά από σύγκριση.

ΧΡΟΝΟΛΟΓΙΚΑ

Ημερομηνία Έτος Γεγονότα 15 Μάιος 1973 Η NBS δημοσιεύει το πρώτο αίτημα για έναν τυποποιημένο αλγόριθμο κρυπτογράφησης 27 Αυγούστου 1974 Η NBS δημοσιεύει ένα δεύτερο αίτημα για τους αλγορίθμους κρυπτογράφησης 17 Μαρτίου 1975 Ο DES δημοσιεύεται στον ομοσπονδιακό κατάλογο για σχόλια Αύγουστος 1976 Δημιουργία του πρώτου εργαστηρίου για τον DES Σεπτέμβριος 1976 Δεύτερο εργαστήριο, που συζητάται το μαθηματικό ίδρυμα DES Νοέμβριος 1976 Ο DES εγκρίνεται ως πρότυπο 15 Ιανουαρίου 1977 Ο DES δημοσιεύεται ως ένα πρότυπο του FIPS, το FIPS PUB 46

1983 Ο DES επιβεβαιώνεται για πρώτη φορά

1986 Το Videocipher ΙΙ, ένα δορυφορικό σύστημα TV που χρησιμοποιείται από την HBO, ανακατεύεται στα συστήματα που βασίζονται σε DES 22 Ιανουαρίου 1988 Ο DES επιβεβαιώνεται για τη δεύτερη φορά ως FIPS 46-1, εκτοπίζοντας τον FIPS PUB 46 Ιούλιος 1990 Οι Biham και Shamir ανακαλύπτουν πάλι την διαφορική κρυπτανάλυση και την εφαρμόζουν σε ένα κρυπτοσύστημα είδους DES 15 κύκλων

1992 Οι Biham και Shamir αναφέρουν την πρώτη θεωρητική επίθεση με λιγότερη πολυπλοκότητα από την brute force, τη διαφορική κρυπτανάλυση. Εντούτοις, απαιτεί 247 μη ρεαλιστικά προεπιλεγμένα plaintexts 30 Δεκεμβρίου 1993 Ο DES επιβεβαιώνεται για τρίτη φορά ως FIPS 46-2

1994 Η πρώτη πειραματική κρυπτανάλυση του DES εκτελείται χρησιμοποιώντας γραμμική κρυπτανάλυση (Matsui, 1994). Ιούνιος 1997 Το πρόγραμμα DESCHALL “σπάει” για πρώτη φορά μπροστά σε κοινό ένα μήνυμα που κρυπτογραφήθηκε με τον DES Ιούλιος 1998 Οι EFF ως DES crackers (Deep Crack) σπάνε ένα κλειδί του DES σε 56 ώρες Ιανουάριος 1999 Μαζί, η Deep Crack και η distributed.net σπάνε ένα κλειδί DES σε 22 ώρες και 15 λεπτά. 25 Οκτωβρίου 1999 Ο DES επιβεβαιώνεται για τέταρτη φορά ως FIPS 46-3, που διευκρινίζει την προτιμημένη χρήση του triple DES με ενιαίο DES που επιτρέπεται μόνο στα κληρονομικά συστήματα 26 Νοεμβρίου 2001 Το AES δημοσιεύεται σε FIPS 197 26 Μαΐου 2002 Το πρότυπο AES γίνεται αποτελεσματικό 26 Ιουλίου 2004 Η απόσυρση του FIPS 46-3 (και μερικών σχετικών προτύπων) προτείνεται στον ομοσπονδιακό κατάλογο 19 Μαΐου 2005 Το NIST αποσύρει τον FIPS 46-3 15 Μαρτίου 2007 Η παράλληλη μηχανή COPACOBANA (βασισμένη σε FPGA) του πανεπιστημίου του Μπόχουμ και του Κίελου της Γερμανίας, σπάνε τον DES σε 6,4 ημέρες με κόστος υλικού $10.000

Η περιγραφή του DES

Ο DES είναι ο αρχετυπικός block cipher, δηλαδή, ένας πρωτότυπος κρυπταλγόριθμος συμμετρικού κλειδιού, που λαμβάνει μια σειρά από plaintext bits (bits απλού κειμένου) σταθερού μήκους και την μετατρέπει μέσω μιας σειράς πολύπλοκων ενεργειών σε μια άλλη σειρά bit, το chiphertext (κρυπτοκείμενο) με το ίδιο μήκος. Στην περίπτωση του DES, το μέγεθος μπλοκ (block size: Η σειρά των bits σταθερού μήκους) είναι 64 bits. Ο DES χρησιμοποιεί επίσης ένα κλειδί για να προσαρμόσει τη μετατροπή, ώστε η αποκρυπτογρά-φηση να μπορεί, υποθετικά, να πραγματοποιηθεί μόνο από εκείνους που γνωρίζουν το συγκεκριμένο κλειδί που χρησιμοποιήθηκε για την κρυπτογράφηση. Το κλειδί φαινομενικά αποτελείται από 64 bits. Ωστόσο, στην πραγματικότητα, μόνο 56 από αυτά χρησιμοποιήθηκαν από τον αλγόριθμο. Τα υπόλοιπα 8 bits χρησιμοποιούνται αποκλειστικά για τον έλεγχο της ισοτιμίας (αρτιότητα) και στη συνέχεια απορρίπτονται. Αυτά τα 8 bits ονομάζονται parity bits. Εξ' ου και αναφέρεται συνήθως ως κλειδί μήκους των 56 bits. Όπως οι άλλοι block αλγόριθμοι κρυπτογράφησης, έτσι και ο DES από μόνος του δεν είναι ένας ασφαλής τρόπος κρυπτογράφησης, αλλά αντίθετα, πρέπει να χρησιμοποιηθεί με ένα ειδικό τρόπο λειτουργίας (mode of operation). Ο FIPS-81 ορίζει πολλούς τρόπους χρήσης με DES. Περαιτέρω παρατηρήσεις σχετικά με τη χρήση του DES περιέχονται στο FIPS-74.

Η γενική δομή

Η γενική δομή του αλγορίθμου παρουσιάζεται στην Εικόνα 1: Υπάρχουν 16 πανομοιότυπα στάδια της επεξεργασίας, που καλούνται Γύροι. Υπάρχει επίσης μια αρχική και μια τελική μεταλλαγή που καλούνται IP και FP (ή IP-1) αντίστοιχα, οι οποίες είναι Αντίστροφες Συναρτήσεις (η IP "ανατρέπει" τη δράση του FP, και αντίστροφα). Η IP και η FP δεν έχουν σχεδόν καμία κρυπτογραφική σημασία, αλλά συμπεριλήφθηκαν προφανώς, προκειμένου να διευκολύνουν τα block φόρτωσης μέσα και έξω από το hardware των μέσων της δεκαετίας του 1970, καθώς επίσης και για να κάνουν τον DES να τρέχει πιο αργά σε λογισμικό. Πριν από τους κύριους γύρους, το block είναι διηρη-μένο σε δύο τριανταδυάμπιτα μισά και επεξεργασμένο διαδοχικά. Αυτή η σταυροειδής διάταξη είναι γνωστή ως σχήμα Feistel (Feistel scheme). Η δομή Feistel εξ-ασφαλίζει ότι η αποκρυπτογράφηση και η κρυπτογρά-φηση είναι πολύ παρόμοιες διαδικασίες. Η μόνη δια-φορά είναι ότι τα subkeys (υποκλείδια ή δευτερεύοντα κλειδιά) εφαρμόζονται στην αντίστροφη διάταξη όταν τίθεται η πράξη της αποκρυπτογράφησης. Το υπό-λοιπο του αλγορίθμου είναι ίδιο. Αυτό απλοποιεί πολύ την εφαρμογή, ιδιαίτερα στο υλικό, δεδομένου ότι δεν υπάρχει καμία ανάγκη για ξέχωρους αλγορίθμους κρυπτογράφησης και αποκρυπτογράφησης. Το κόκκινο το σύμβολο δείχνει την αποκλειστική OR (XOR) λειτουργία. Η F συνάρτηση ανακατώνει το μισό τμήμα του block μαζί με ένα μέρος από το κλειδί. Η έξοδος από την συνάρτηση F συνδυάζεται έπειτα με το άλλο μισό του block και τα μισά ανταλλάσσονται πριν από τον επόμενο κύκλο. Μετά από τον τελικό γύρο, τα μισά δεν ανταλλάσσονται, αυτό είναι ένα χαρακτηριστικό γνώρισμα της δομής Feistel που κάνει την κρυπτογράφηση και την αποκρυπτογράφηση παρόμοιες διαδικασίες.

Η συνάρτηση Feistel (F)

Η συνάρτηση F, που απεικονίζεται στην Εικόνα 2, λειτουργεί με μισό block (32 bits) τη φορά και αποτελείται από τέσσερα στάδια:

Επέκταση → Το τριανταδυάμπιτο μισό block έχει επεκταθεί σε 48-bit χρησιμοποιώντας την επεκτατική μεταλλαγή (expansion permutation) – η οποία υπάρχει με την ονομασία Ε (γαλάζιο ορθογώνιο) στην Εικόνα 2 – αντιγράφοντας ορισμένα από τα bits.

Ανάμειξη κλειδιών → Το αποτέλεσμα αναμιγνύεται με ένα subkey με τη χρήση μιας XOR λειτουργίας/πράξης. Δεκαέξι σαρανταοκτάμπιτα κλειδιά – ένα για κάθε γύρο - προέρχονται από το κύριο κλειδί χρησιμοποιώντας το χρονοδιάγραμμα / πρόγραμμα κλειδιού (key schedule) το οποίο θα περιγραφεί παρακάτω.

Αντικατάσταση → Μετά την ανάμειξη με το subkey, το block διαιρείται σε οκτώ 6-bit κομμάτια πριν να επεξεργαστούν από τα S-boxes (Substitution boxes – κουτιά αντικατάστασης). Κάθε ένα από τα οκτώ S-boxes αντικαθιστά τις εξάμπιτες εισόδους του με εξόδους των 4ων bits σύμφωνα με ένα μη γραμμικό μετασχηματισμό, που παρέχεται με τη μορφή ενός πίνακα αναζήτησης (lookup table). Τα S-boxes παρέχουν τον πυρήνα της ασφάλειας του DES – χωρίς αυτά, ο κρυπταλγόριθμος θα ήταν γραμμικός και κοινότοπα εύθραυστος. 

Μεταλλαγή → Τέλος, οι 32 έξοδοι από το S-boxes διακανονίζονται σύμφωνα με μια σταθερή μεταλλαγή, το P-box.

Η εναλλαγή της αντικατάστασης από τα S-boxes και τη μεταλλαγή των bits από το P-box και την E-expansion (επέκταση), παρέχει τη λεγόμενη “σύγχυση (μπέρδεμα) και διάχυση” αντίστοιχα, μια έννοια που προσδιορίζεται από τον Claude Shannon τη δεκαετία του 1940 ως απαραίτητη προϋπόθεση για έναν ασφαλή και πρακτικό πλέον κρυπταλγόριθμο.

Κάντε κλικ εδώ

Το πρόγραμμα κλειδιού

H Εικόνα 3 απεικονίζει το πρόγραμμα κλειδιού για την κρυπτογράφηση — ο αλγό-ριθμος που δημιουργεί τα subkeys. Αρχικά, 56 bits του κλειδιού επιλέγονται από τα αρχικά 64 από τη μεταλλαγμένη επιλογή 1 (Permuted Choice 1 : PC-1) — τα υπόλοιπα οκτώ bits είτε απορρίπτονται είτε χρησιμοποιούνται ως parity bits (για τον έλεγχο ισοτιμίας). Τα 56 bit διαιρούνται έπειτα σε δύο μισά 28μπιτα, κάθε μισό αντιμετωπίζεται έκτοτε χωριστά. Στους διαδοχικούς γύρους και τα δύο μισά περιστρέ-φονται αριστερά κατά ένα ή δύο bits (που διευκρινίζονται για κάθε γύρο) και έπειτα, 48 bits του subkey επιλέγονται από τη μεταλλαγμένη επιλογή 2 (Permuted Choice 2 : PC-2) — 24 bits από το αριστερό μισό και 24 από το δεξιό μισό. Οι περιστροφές (που δείχνονται από το <<< στην Εικόνα 3) σημαί-νουν ότι ένα διαφορετικό σετ απο bits χρησι-μοποιείται σε κάθε subkey. Κάθε bit χρησι-μοποιείται σε περίπου 14 από τα 16 subkeys. Το πρόγραμμα κλειδιού για την αποκρυπτο-γράφηση είναι παρόμοιο — τα subkeys είναι στην αντίστροφη διάταξη έναντι αυτή της κρυ-πτογράφησης. Αν δηλαδή κατά την κρυπτο-γράφηση το πρόγραμμα κλειδιού είναι {k1, k2, k3 ... k16}, τότε το πρόγραμμα κλειδιού της αποκρυπτογράφησης θα είναι {k16 ... k3, k2, k1}. Πέραν αυτής της αλλαγής, η διαδικασία είναι η ίδια όπως για την κρυπτογράφηση. Ασφάλεια και κρυπτανάλυση

Αν και οι περισσότερες πληροφορίες που έχουν δημοσιευθεί είναι για την κρυπτανά-λυση του DES απ' ότι οποιουδήποτε άλλου block cipher, η πρακτικότερη επίθεση μέχρι και σήμερα είναι ακόμα η προσέγγιση brute force (ωμής βίας). Διάφορες δευτερεύουσες κρυπταναλυτικές ιδιότητες είναι γνωστές και τρεις θεωρητικές επιθέσεις είναι δυνατές˙ που ακόμα κι αν έχουν μια θεωρητική πολυπλοκότητα μικρότερη από την επίθεση brute-force, απαιτείται να φέρουν ένα ιλιγγιώδες ποσό γνωστών ή προεπιλεγμένων plaintext και δεν αποτελούν ανησυχία στην πράξη.

Επίθεση brute-force (ωμής βίας)

Για οποιοδήποτε κρυπταλγόριθμο, η πιο βασική μέθοδος επίθεσης είναι η brute force — δοκιμάζοντας συνεχόμενα κάθε πιθανό κλειδί - Το μήκος του κλειδιού καθορίζει το πλήθος των πιθανών κλειδιών και ως εκ τούτου τη δυνατότητα πραγματοποίησης αυτής της προσέγγισης. Ερωτήσεις τέθηκαν από νωρίς για την επάρκεια του μήκους κλειδιού του DES πριν ακόμα υιοθετηθεί ως πρότυπο. Το μικρό μήκος κλειδιού ήταν αυτό που στην ουσία διέταξε την ανάγκη για την αντικατάσταση του αλγόριθμου, παρά η θεωρητική κρυπτανάλυση. Είναι γνωστό ότι η NSA ενθάρρυνε, αν δεν έπεισε, την ΙΒΜ για να μειώσει το μήκος του κλειδιού από τα 128 bits στα 64 bits και από εκεί σε 56 bits. Αυτό λαμβάνεται συχνά ως ένδειξη ότι η NSA σκέφτηκε ότι θα ήταν σε θέση να “σπάσει” τα κλειδιά αυτού του μήκους ακόμη και στα μέσα της δεκαετίας του '70. Στον ακαδημαϊκό κόσμο, έγιναν διάφορες προηγμένες προτάσεις για μια μηχανή που θα αποσκοπούσε στο να “σπάει” τον DES. Το 1977, οι Diffie και Hellman πρότειναν μια μηχανή που κοστίζει κατ' εκτίμηση 20 εκατομμύρια δολάρια η οποία θα μπορούσε να βρει ένα κλειδί DES σε μία και μόνο ημέρα. Μέχρι το 1993, ο Wiener είχε προτείνει μια μηχανή αναζήτησης κλειδιού με κοστολόγηση 1 εκατομμύριο δολάρια που θα έβρισκε ένα κλειδί μέσα σε 7 ώρες. Εντούτοις, καμία από αυτές τις πρόωρες προτάσεις δεν εφαρμόστηκε˙ τουλάχιστον καμία εφαρμογή δεν αναγνωρίστηκε δημόσια. Η ευπάθεια του DES επιδείχθηκε πρακτικά προς το τέλος της δεκαετίας του '90. Το 1997, η εταιρεία RSA Security υποστήριξε μια σειρά διαγωνισμών, που προσέφερε ένα βραβείο $10.000 στην πρώτη ομάδα που θα “έσπαγε” ένα μήνυμα το οποίο κρυπτογραφήθηκε με τον DES για το διαγωνισμό. Εκείνος ο διαγωνισμός κερδήθηκε από το πρόγραμμα DESCHALL, που οδηγήθηκε από Rocke Verser, τον Matt Curtin, και τον Justin Dolske, χρησιμοποιώντας ιδανικούς κύκλους χιλιάδων υπολογιστών σε ολόκληρο το Διαδίκτυο. Η δυνατότητα πραγματοποίησης του “σπάσιμου” του DES γρήγορα καταδείχθηκε το 1998 όταν φτιάχτηκε μια “DES-σπάστης” συνήθειας από την EFF (Electronic Frontier Foundation), μια ομάδα αστικών δικαιωμάτων κυβερνοχώρου, με κόστος περίπου $250,000 (Εικόνα 4). Το κίνητρό τους ήταν να δείξουν ότι ο DES ήταν το ίδιο εύθραυστος στην πράξη όπως και στην θεωρία:

"Υπάρχουν πολλοί άνθρωποι που δεν θα πιστέψουν μια αλήθεια έως ότου μπορούν να τη δουν με τα μάτια τους. Δείχνοντάς τους μία φυσική μηχανή που μπορεί να “σπάσει” τον DES σε μερικές ημέρες είναι ο μόνος τρόπος να πειστούν μερικοί άνθρωποι ότι δεν μπορούν να εμπιστευθούν την ασφάλειά τους στον DES."

Η μηχανή εμφάνισε ένα κλειδί με χρήση brute force σε κάτι περισσότερο από 2 ημέρες. Περόπου στον ίδιο χρόνο ένας πληρεξούσιος από το αμερικανικό Υπουργείο Δικαιοσύνης ανήγγελλε ότι ο DES ήταν άθραυστος.

Η μόνη άλλη επιβεβαιωμένη μηχανή που “έσπαγε” τον DES ήταν η μηχανή COPACOBANA (σύντμηση του βέλτιστου κόστους και παράλληλα ενός code breaker) που χτίστηκε πιο πρόσφατα από τις ομάδες των πανεπιστημίων του Μπόχουν και του Κίελου της Γερμανίας. Αντίθετα από τη μηχανή της EFF, η COPACOBANA αποτελείται από τα εμπορικά διαθέσιμα, ανασχηματισμένα ολοκληρωμένα κυκλώματα. 120 αυτών των FPGAs του τύπου XILINX Spartan3-1000 τρέχουν σε παράλληλη σύνδεση. Ομαδοποιούνται σε 20 DIMM ενότητες, που κάθε μια περιέχει 6 FPGAs. Η χρήση των ανασχηματισμένων hardware κάνει την μηχανή εφαρμόσιμη και σε άλλες λειτουργίες για “σπάσιμο” κωδικών. Η Εικόνα 5 δείχνει μία πλήρη μηχανή COPACOBANA. Μια από τις πιό ενδιαφέρουσες πτυχές COPACOBANA είναι ο παράγοντας του κόστους της. Μια μηχανή μπορεί να φτιαχτεί για περίπου $10.000. Η μείωση κόστους από έναν κατά προσέγγιση παράγοντα της τάξης των 25% από αυτή της μηχανής της EFF είναι ένα εντυπωσιακό παράδειγμα για τη συνεχή βελτίωση του ψηφιακού υλικού. Κατά ενδιαφέροντα τρόπο ο νόμος του Moore προβλέπει μια βελτίωση της τάξης περίπου 32%, δεδομένου ότι περίπου 8 έτη έχουν μεσολαβήσει μεταξύ του σχεδιασμού των δύο μηχανών, πράγμα το οποίο επιτρέπει περίπου πέντε διπλασιασμούς της δύναμης υπολογιστών (ή 5 μειώσεις τις τάξεως του 50% του κόστους για τον ίδιο υπολογισμό).

Επιθέσεις γρηγορότερες από την brute - force

Υπάρχουν τριων ειδών επιθέσεις που είναι γνωστό οτι μπορούν να “σπάσουν” ΚΑΙ τους δέκα έξι γύρους του DES με λιγότερη πολυπλοκότητα από μια αναζήτηση brute force:

Η Διαφορική Κρυπτανάλυση (Differential Cryptanalysis – DC)

Η Γραμμική Κρυπτανάλυση (Linear Cryptanalysis - LC) και τέλος

Η επίθεση του Davie (Davies' Attack)

Εντούτοις, οι επιθέσεις είναι θεωρητικές και είναι αδύνατο να τοποθετηθούν στην πράξη. Τέτοιου είδους επιθέσεις καλούνται μερικές φορές Certificational Weaknesses.

Δευτερεύουσες κρυπταναλυτικές ιδιότητες

Ο DES εκθέτει την ιδιοκτησία συμπλήρωσης, δηλαδή:

Όπου είναι το συμπλήρωμα του Χ. Το ΕΚ δείχνει την κρυπτογράφηση με κλειδί Κ. Τα P και C δείχνουν το plaintext και το chiphertext αντίστοιχα. Η ιδιοκτησία συμπλήρωσης σημαίνει ότι η εργασία για μια επίθεση brute force θα μπορούσε να μειωθεί κατά έναν παράγοντα της τάξης του 2 (ή ένα bit) σε μία περίπτωση προεπιλεγμένου plaintext. Ο DES έχει επίσης τέσσερα αποκαλούμενα αδύναμα κλειδιά. Η κρυπτογράφηση (Ε) και η αποκρυπτογράφηση (D) υπό ένα αδύναμο κλειδί έχουν την ίδια επίδραση: ΕΚ(ΕΚ(P)) = P ή ισοδύναμα, EΚ = DΚ Υπάρχουν επίσης έξι ζευγάρια των ημι-αδύναμων κλειδιών. Η κρυπτογράφηση με το ένα από το ζευγάρι των ημιαδύναμων κλειδιών, Κ1, λειτουργεί όμοια στην αποκρυπτογράφηση με άλλο, Κ2:

            ή ισοδύναμα,