An dieser Stelle findest du eine kleine Sammlung einfacher Probleme aus dem Bereich der Informationssicherheit. Diese Probleme sind absichtlich einfach gehalten und erfordern kein Vorwissen, auch wenn Grundwissen in Programmieren und ein gewisses mathematisches Verständnis sicher hilfreich sind.

Die folgenden Online Tests bieten wir zurzeit an:

Wir haben die anspruchsvolleren Tests mit ihrem Schwierigkeitsgrad gekennzeichnet:

  • (*) Etwas anspruchsvoller
  • (**) Sehr anspruchsvoll

Caesar-Chiffre

Kryptographische Methoden um Nachrichten zu verschlüsseln sind schon seit der Antike im Einsatz. Eine der ersten Verschlüsselungsmethoden war die Caesar-Chiffre, benannt nach dem römischen Feldherren Julius Gaius Caesar. Bei der Caesar-Chiffre handelt es sich um eine Substitutions-Chiffre, d.h. jeder Buchstabe der ursprünglichen Nachricht ("Klartext") wird durch einen anderen Buchstaben ersetzt um den Chiffretext ("Geheimtext" oder "Chiffrat") zu erzeugen. Eine Unterform der Substitutions-Chiffre ist die Verschiebe-Chiffre. Dabei wird jeder Buchstabe durch den Buchstaben im Alphabet ersetzt, der eine bestimmte Anzahl Positionen weiter vorne (oder weiter hinten) im Alphabet steht. Dieser Abstand, um den die Buchstaben bewegt werden, nennt man Schlüssel. Wenn es dabei zu einem Überlauf kommt, z.B. also beim Verschieben des Z um eine Position, fängt man vorne im Alphabet wieder an (Z wird also zu A). Die Entschlüsselung funktioniert analog durch rückwärtiges Verschieben. Bei der Caesar-Chiffre ist der Schlüssel festgelegt auf 3. Bild 1 illustriert die Verschlüsselung des Alphabets.

Caesar Chiffre mit einem Rechts-Shift von 3
Bild 1: Prinzip der Caeser-Chiffre

Berechnung

Eine der Schwachstellen der Caesar-Chiffre ist, dass jeder Buchstabe immer auf genau denselben Buchstaben des Chiffre-Alphabets abgebildet wird (" monoalphabetische Chiffre"). Als Folge dessen erhält die Caesar-Chiffre die Texteigenschaften des Klartexts im Chiffre-Text aufrecht, insbesondere die Frequenz der einzelnen Buchstaben. Wenn man also beispielsweise weiß, dass 8% der Buchstaben des Klartextes ein "E" sind, dann stellt die Substitution von "E" ebenfalls 8% der Buchstaben im Chiffrat dar. Diese Textcharakteristika sind normalerweise abhängig von der Sprache des Klartexts. Zum Beispiel sind ca. 13% der Buchstaben eines englischen Texts ein "E". Statistiken zu den Buchstabenhäufigkeiten verschiedener Sprachen können u.a. auf Wikipedia gefunden werden. Diese Eigenschaft der Caesar-Chiffre erlaubt eine Frequenzanalyse der Buchstabenhäufigkeiten des Chiffrats und das Ableiten des Schlüssels. Wenn man also davon ausgeht, dass ein Klartext im Original englisch war und im Chiffrat ist "X" der häufigste Buchstabe, dann lässt dies vermuten, dass "X" die Substitution von "E" ist.

Natürlich kann man auch einfach alle Kombinationen ausprobieren, d.h. einfach alle potentiellen Klartexte erzeugen, indem man jeden der 26 möglichen Schlüssel probiert. Der richtige Klartext ist dann leicht erkennbar (unter der Annahme, dass der Klartext ein sinnvoller Text war und nicht eine zufällige Zeichenfolge). Mit Hilfe eines Computers ist dieses Brechen der Chiffre eine Sache von Millisekunden.

Aufgaben

Im Folgenden haben wir eine Nachricht gepostet, die mit der Caesar-Chiffre verschlüsselt wurde. Deine Aufhabe ist es den Schlüssel herauszufinden.
Ein paar Anmerkungen zu dem Chiffrat und Klartext:
  1. Der Klartext ist englisch und enthält somit keine Umlaute oder Eszett
  2. Der Klartext und das Chiffre-Alphabet bestehen nur aus Großbuchstaben
  3. Um die Satzstruktur zu verstecken haben wir sämtliche Interpunktionszeichen inkl. Leerzeichen entfernt und den Chiffretext nur zur optischen Veranschaulichung auf dieser Webseite in Blöcke von je 5 Buchstaben unterteilt
  4. Zahlen wurden nicht verschlüsselt und sind im Klartext und Chiffretext identisch
  5. Um die Buchstabenhäufigkeit zu ermitteln gibt es Online-Tools, z.B. hier
PJRDB SDURD BLJNB JAFJB JAXVJ WPNWN AJUBC JCNBV JWLXW BDUJW MWXCJ KUNJD CQXAX OUJCR WYAXB NQNYU JHNMJ LARCR LJUAX UNRWC QNNEN WCBCQ JCUNM CXCQN MNVRB NXOCQ NAXVJ WANYD KURLJ WMCQN ARBNX OCQNA XVJWN VYRAN RW60K LLJNB JALAJ BBDBJ WMYXV YNHOX AVNMJ YXURC RLJUJ UURJW LNCQJ CFJBC XMXVR WJCNA XVJWY XURCR LBOXA BNENA JUHNJ ABCQN RAJCC NVYCB CXJVJ BBYXF NACQA XDPQY XYDUR BCCJL CRLBF NANXY YXBNM KHCQN LXWBN AEJCR ENADU RWPLU JBBFR CQRWC QNAXV JWBNW JCNJV XWPCQ NVLJC XCQNH XDWPN AFRCQ CQNOA NZDNW CBDYY XACXO LRLNA XLJNB JABER LCXAR NBRWC QNPJU URLFJ ABLXV YUNCN MKH51 KLNGC NWMNM AXVNB CNAAR CXAHC XCQNN WPURB QLQJW WNUJW MCQNA QRWNL JNBJA KNLJV NCQNO RABCA XVJWP NWNAJ UCXLA XBBKX CQFQN WQNKD RUCJK ARMPN JLAXB BCQNA QRWNJ WMLXW MDLCN MCQNO RABCR WEJBR XWXOK ARCJR WCQNB NJLQR NENVN WCBPA JWCNM QRVDW VJCLQ NMVRU RCJAH YXFNA JWMCQ ANJCN WNMCX NLURY BNCQN BCJWM RWPXO YXVYN HFQXQ JMANJ URPWN MQRVB NUOFR CQCQN BNWJC NJOCN ACQNM NJCQX OLAJB BDBRW 53KLF RCQCQ NPJUU RLFJA BLXWL UDMNM CQNBN WJCNX AMNAN MLJNB JACXB CNYMX FWOAX VQRBV RURCJ AHLXV VJWMJ WMANC DAWCX AXVNL JNBJA ANODB NMJWM VJATN MQRBM NORJW LNRW4 9KLKH LAXBB RWPCQ NADKR LXWFR CQJUN PRXWU NJERW PQRBY AXERW LNJWM RUUNP JUUHN WCNAR WPAXV JWCNA ARCXA HDWMN AJAVB LRERU FJAAN BDUCN MOAXV FQRLQ QNNVN APNMJ BCQND WAREJ UNMUN JMNAX OAXVN JOCNA JBBDV RWPLX WCAXU XOPXE NAWVN WCLJN BJAKN PJWJY AXPAJ VXOBX LRJUJ WMPXE NAWVN WCJUA NOXAV BRWLU DMRWP CQNLA NJCRX WXOCQ NSDUR JWLJU NWMJA QNLNW CAJUR BNMCQ NKDAN JDLAJ LHXOC QNANY DKURL JWMFJ BNENW CDJUU HYAXL UJRVN MMRLC JCXAR WYNAY NCDRC HKDCC QNDWM NAUHR WPYXU RCRLJ ULXWO URLCB QJMWX CKNNW ANBXU ENMJW MXWCQ NRMNB XOVJA LQ44K LLJNB JAFJB JBBJB BRWJC NMKHJ PAXDY XOBNW JCXAB UNMKH VJALD BSDWR DBKAD CDBJW NFBNA RNBXO LRERU FJABK AXTNX DCJWM CQNLX WBCRC DCRXW JUPXE NAWVN WCXOC QNANY DKURL FJBWN ENAAN BCXAN MLJNB JABJM XYCNM QNRAX LCJER JWUJC NATWX FWJBJ DPDBC DBAXB NCXBX UNYXF NAJWM CQNNA JXOCQ NAXVJ WNVYR ANKNP JWVDL QXOLJ NBJAB URONR BTWXF WOAXV QRBXF WJLLX DWCBX OQRBV RURCJ AHLJV YJRPW BJWMO AXVXC QNALX WCNVY XAJAH BXDAL NBVJR WUHCQ NUNCC NABJW MBYNN LQNBX OLRLN AXJWM CQNQR BCXAR LJUFA RCRWP BXOBJ UUDBC CQNUJ CNAKR XPAJY QRNBX OLJNB JAKHB DNCXW RDBJW MYUDC JALQJ ANJUB XVJSX ABXDA LNBLJ NBJAR BMNNV NMCXK NXWNX OCQNP ANJCN BCVRU RCJAH LXVVJ WMNAB RWQRB CXAH

BXDAL NFRTR YNMRJ

Um zu testen, ob du den richtigen Schlüssel gefunden hast, entschlüssele den folgenden Text mit dem Schlüssel, den du überprüfen willst, und gib den Klartext in das folgende Formular ein:

NRERNLJWPRNANRCJNIRNSNRKJJCQDRTX
Bei der Caesar-Chiffre kann man die Substitution aller Buchstaben leicht ableiten, sobald man ein korrektes Substitutionspaar gefunden hat. Als zweiten Test haben wir daher eine einfache Substitutions-Chiffre gewählt, bei der die Substitution von Klartextbuchstaben zufällig gewählt wurde (aber noch eindeutig ist). Wie in Bild 2 illustriert bedeutet das, dass es keine offensichtlichen Zusammenhänge mehr zwischen den Substitutionen gibt. Der Schlüssel ist somit das Wissen wie jeder Buchstabe ersetzt wird.
Einfache Substitutionschiffre mit randomisierter Abbildung zwischen Klartext und Chiffretext
Bild 2: Beispiel einer einfachen randomisierten Substitutionschiffre (monoalphabetisch).
Es gelten die selben Anmerkungen wie bei Test 1 und es ist wieder deine Aufgabe den Schlüssel für den folgenden Chiffretext zu finden: PNRQE EOHEJ DMQZJ RZBVR OTEJA QQMCP RRJBR DROEH QPEPR QLMPN MPQIE UMPEH EPQEE OGOWR IKRJM PNEQE JEORE ZB257 0QYTE JD101 2000M JNEGM PEJPQ MJPRO TQZBG ZPNEO REEJD UZUWH EPMZJ QMFRE UEOPB OZTPN RIMPA -QPEP RQZBG ROHMJ GORTR JEJDN ETGWO VMPMQ VROTE JAQQT EHHRQ PBRDR OEHQP EPRPN RLREH PNZBM PQIZE HDRUZ QMPQE JDPNR MOHEO VR-QI EHRMJ DWQPO MEHRC UHZMP EPMZJ IZWUH RDLMP NMPQH ZIEPM ZJZJP NRGZO DROGR PLRRJ BOEJI REJDV ROTEJ ANEXR VMXRJ PNRQE EOHEJ DEWJM YWRNM QPZOA MJTZD ROJPM TRQUO MZOPZ MPQIO REPMZ JEQPN RPROO MPZOA ZBPNR QEEOG EQMJG APNRH REVWR ZBJEP MZJQE BPROL ZOHDL EOMPN RQEEO HEJDD MDJZP RCMQP EQEWJ MBMRD RJPMP AWJPM HPNRJ QZTRU EOPQZ BMPNE DGRRJ UOWQQ MEJLN MHRZP NROQG RHZJV RDPZG EXEOM EPNRM JNEGM PEJPQ XZPRD PZORS ZMJVR OTEJA MJEUH RGMQI MPRNR HDMJ1 935BO ZT194 7PZ19 56PNR QEEOH EJDLE QEBOR JIN-Z IIWUM RDPRO OMPZO AQRUE OEPRB OZTPN RORQP ZBVRO TEJAG RPLRR J1950 EJD19 56QEE OHEJD LEQET RTGRO ZBPNR IZWJI MHZBR WOZUR MJ195 5MJEJ ZPNRO UHRGM QIMPR PNRMJ NEGMP EJPQL RORZB BRORD MJDRU RJDRJ IRGWP XZPRD MJQPR EDBZO PNRPR OOMPZ OAPZG RIZTR EQPEP RZBLR QPVRO TEJAB OZT19 20PZ1 935EJ DEVEM JBOZT 1947P Z1959 PNRMJ NEGMP EJPQZ BPNRQ EEOHE JDWQR DUZQP EVRQP ETUQM QQWRD QURIM EHHAB ZOPNR PROOM PZOAQ RRUZQ PEVRQ PETUQ EJDUZ QPEHN MQPZO AZBPN RQEEO BZODR PEMHQ

QZWOI RLMKM URDME

Entschlüssele dann den folgenden kurzen Text mit dem Schlüssel, den du überprüfen willst, und nutze das Formular um dein Ergebnis zu überprüfen:

RMLZNCRMCZNZNHENYWWKWMQNEINRRBRE

Vigenère-Chiffre

Beschreibung

Die Vigenère-Chiffre wurde von Blaise de Vigenère erfunden, einem Kryptologen des 16ten Jahrhunderts. Sie ist ebenfalls eine Substitutions-Chiffre, jedoch im Gegensatz zur Caesar-Chiffre polyalphabetisch. Das bedeutet, dass die Chiffre mehrere Chiffre-Alphabete verwendet und Buchstaben des Klartexts durch Buchstaben aus unterschiedlichen Chiffre-Alphabeten substituiert werden. Bild 1 zeigt das Prinzip der Vigenère-Chiffre. Vereinfacht kann man sich dieses Prinzip so vorstellen, dass jeder Buchstabe des Klartexts mit einer Verschiebe-Chiffre verschlüsselt wird, wobei der aktuelle Buchstabe des Schlüsselwortes der Schlüssel für diese Verschiebe-Chiffre ist. Für Bild 1 heißt das, dass der erste Buchstabe "W" des Klartextes mit einer Verschiebe-Chiffre mit Schlüssel "S" verschlüsselt wird; der zweite Buchstabe "H" dann mit dem Schlüssel "E", usw. Da der Schlüssel für die Vigenère-Chiffre (hier das Wort "SECURITY") normalerweise kürzer ist als der Klartext, wird der Schlüssel einfach solange wiederholt, bis alle Buchstaben des Klartextes verschlüsselt wurden. Um das manuelle Ver- und Entschlüsseln zu erleichtern, gibt es das Vigenère-Quadrat (siehe Bild 2), welches ein leichtes Ablesen der Substitution für den aktuellen Buchstaben des Schlüssels erlaubt (d.h., jede Zeile des Vigenère-Quadrats zeigt die Verschiebe-Chiffrierung für einen Schlüssel aus dem Alphabet A-Z, wobei A=1, B=2, usw.).

Das Ziel dieser polyalphabetischen Substitution ist es, eine einfache Frequenzanalyse, wie sie bei der Caesar-Chiffre möglich war, zu verhindern. In Bild 1 zum Beispiel wird der Buchstabe "T" des Klartextes beim ersten Mal durch "N" substituiert, bei zweiten Mal jedoch durch "R". Da nun Buchstaben des Klartextes nicht immer auf denselben Buchstaben des Chiffretextes abgebildet werden, werden die Textcharakteristika wie Buchstabenhäufigkeit nicht mehr durch die Verschlüsselung erhalten und somit verrät eine Frequenzanalyse des Chiffretextes keine Information über den verwendeten Schlüssel oder Klartext.

Beispiel für Vigenere Chiffre
Bild 1: Beispiel für Verschlüsselung mit der Vigenère-Chiffre.
Vigenere Quadrat
Bild 2: Vigenère-Quadrat zum Ver- und Entschlüsseln von Texten mit der Vigenère-Chiffre.
(Quelle: Cryptool Online)

Berechnung

Auch wenn eine Frequenzanalyse wie bei der Caesar-Chiffre nicht mehr möglich ist, kann man aus einer Untersuchung des Chiffretextes Rückschlüsse auf den verwendeten Schlüssel ziehen und die Vigenère-Chiffre brechen. Die wichtigste Erkenntnis hier ist, dass man im Chiffretext Muster erkennen kann, die direkt abhängig von der Länge des Schlüssel(worte)s sind. Bild 3 illustriert dieses Prinzip für das Beispiel in Bild 1.

Beispiel für Vigenere Chiffre
Bild 3: Beispiel für Muster im Chiffretext.

In Bild 3 kann man erkennen, dass der Chiffretext zweimal die Zeichenfolge "PTR" enthält. Dies ist die Folge davon, dass zufällig zweimal dieselbe Buchstabenfolge im Klartext ("HAT") mit derselben Buchstabenfolge des Schlüsselwortes ("ITY") verschlüsselt wurde. Dies kann passieren, weil zum einen der Klartext aus sinnvollen Wörtern besteht, die sich leicht wiederholen können (z.B. Artikel wie "der", "die", "das"), und zum anderen das Schlüsselwort in der Regel (wesentlich) kürzer ist als der Chiffretext und somit immer wieder wiederholt werden muss um, den gesamten Klartext zu verschlüsseln.

Die entscheidende Konsequenz dieser Muster ist, dass sie Rückschlüsse auf die Schlüssellänge zulassen. Damit ein Fall wie in Bild 3 eintreten kann, muss der Abstand zwischen den Mustern gleich einem Vielfachen der Schlüssellänge sein. Das bedeutet, dass wenn man bei langen Chiffretexten mehrere solcher Buchstabenfolgen findet. die sich in bestimmten Abständen wiederholen, dann muss die richtige Schlüssellänge ein Teiler all dieser gefundenen Abstände sein.

Sobald man eine Vermutung über die Schlüssellänge hat, kann man die Vigenère-Chiffre brechen, indem man das Schlüsselwort Buchstabe für Buchstabe bestimmt. Jeder Buchstabe kann durch das Brechen einer simplen Verschiebe-Chiffre bestimmt werden: Angenommen man vermutet wie in Bild 3, dass die Schlüssellänge ein Teiler von 8 sein muss. Die Längen 1 und 2 scheinen zu kurz zu sein für ein ordentliches Schlüsselwort und werden nicht weiter verfolgt (in der Tat, bei einer Länge von 1 wäre die Vigenère-Chiffre gleich einer einfachen Verschiebe-Chiffre). Wir überspringen an dieser Stelle auch die Länge 4 und nehmen nun also an, dass der Schlüssel 8 Buchstaben lang ist. Dann unterteilt man den Chiffretext in 8 Subtexte, wobei der erste Subtext jeden 8ten Buchstaben des Chiffretext enthält, ausgehend vom ersten Buchstaben; der zweite Subtext jeden 8ten Buchstaben ausgehend vom 2ten Buchstaben; usw., bis zum achten Subtext, der jeden 8ten Buchstaben ausgehend vom 8ten Buchstaben enthält. Dies bedeutet, dass der erste Subtext gleich einem Chiffretext einer einfachen Verschiebe-Chiffre ist, dessen Schlüssel der erste Buchstabe des Vigenère Schlüssels ist. Für das Beispiel in Bild 3 wären die ersten beiden Buchstaben dieses ersten Subtextes also "OT" und man nimmt an, dass sie beide mit einer Verschiebe-Chiffre mit demselben Schlüssel verschlüsselt wurden. Wie man in Bild 3 schon direkt sehen kann, ist diese Annahme richtig und der Schlüssel der Verschiebe-Chiffre ist "S". Der zweite Subtext ist dann gleich dem Chiffretext einer Verschiebe-Chiffre, bei der der Schlüssel gleich dem zweiten Buchstaben des Vigenère Schlüssels ist, usw. Nun kann die Verschiebe-Chiffre für jeden der Subtexte einzeln gebrochen werden und aus den resultierenden Schlüsseln der Subtexte der Vigenère-Schlüssel rekonstruiert werden.

Zusammengefasst sind dies die einzelnen Schritte zum Brechen der Vigenère-Chiffre:

  1. Finde Muster im Chiffretext, die sich wiederholen
  2. Bestimme die Abstände zwischen gleichen Mustern (wie in Bild 3 illustriert)
  3. Die Schlüssellänge muss ein Teiler aller Abstände sein
  4. Für jede mögliche Schlüssellänge n unterteile den Chiffretext in n Subtexte, wobei der erste Subtext jeden n-ten Buchstaben des Chiffretexts enthält, der zweite Subtext jeden (n+1)ten Buchstaben, usw.
  5. Für jeden der Subtexte führe ein Brechen einer Verschiebe-Chiffre basierend auf einer Frequenzanalyse durch
  6. Rekonstruiere den Vigenère-Schlüssel aus diesen Verschiebe-Schlüsseln. Teste ob dieser Schlüssel den Chiffretext erfolgreich entschlüsselt (z.B. einen sinnvollen Text ergibt). Ansonsten wiederhole Schritte 4-6 für eine andere mögliche Schlüssellänge.

Aufgaben

Im Folgenden haben wir einen Auszug aus einer berühmten englischen Kurzgeschichte dargestellt, der mit der Vigenère-Chiffre verschlüsselt wurde. Deine Aufgabe ist es die Chiffre zu brechen und den Schlüssel zu bestimmen. Ein paar Anmerkungen zu dem Chiffretext und Klartext:
  • Der Klartext ist englisch und enthält somit keine Umlaute.
  • Wir haben die ursprüngliche Textstruktur inkl. Satzzeichen erhalten, um die Entschlüsselung etwas zu erleichtern. Satzzeichen wurden nicht substituiert.
  • Verschiedene Tools existieren, um häufige Buchstabenfolgen (N-Gramme) zu finden. (Zum Beispiel Crypto Tool, Analysis→ Tools for Analysis→ N-Gram )
K bzxnm bzpt cb lwav babe pwft oh ck fukbw qenqwkef qf ihg Babe Oiuwipm. Lwe hiui iu, bzt Tkuw Ircdwalgz ops qvw df vpghe omf lhq ijt tqw uaexmj io dm ttlkmntd: awm cexmj uenb lwav ggj sce sal twmcd jqe; now idlaaa kjsrmuief agbe uctilg zwhetdw, hoom acggvmxta qf pmdckw, bgpacd jqk aueqv urcvcceua. Zpd Hqdqy upgln vpw bofmd pnf mpelcqftd vpw bavbwg ip bzt Tkuw Ircdwalgz'k lotlk, le upgjlf pske upgln jqe uat twhs ukwetkkahm. Hwj le upgjlf pske rmjrekdws hka edtkdwh; a rwjz-bwbuwet kgjlf cfsetalpnf Naaba. Jmi tjm Lxmg Bjpvgtdtr jiv botm lwap i lduep gu wjqe pmqvy wiu mdtmgvlh, apl ot dkalguubws hku. Lwipok ihcb odunl zpvg usse vpw urcuw df c twhs etwket usc sgmetd vzarku qf wiu pscdu. Ql xs c uahtcsw io fw lwipok ioq mshing. Lwe umjxowa htortw lhq bgdk jqe hetqgjsng ftvgz xtlv ymxtg amge qn zxs fmhdrvuwct: vpwn wgzw hoomzdw cesge vpsi ttckiipo lwekz jtpwbsiiqvk uot rmsgomfi wkbz wio esh lksw uutvahhkvy p nwzktra eaih goyhhgtd rhkvs. Ho K lgc't vpack cvq df wa kpif dwgy ocuw adwmi tkuw ircdwalkvy xn vpw xnvmjkan jwiwgmf ihcb Lwutavpy cvv ihg vwmt, vpgjgj qlh ofl hdtgvlxanqlxeu zsc, nq lgjbv, qf boub gu owz exnfa: ais rtsjskjaaivg, lwav qk, xtu xjpcvqupl kvugefqtaepmkh, tjm ujrkwmh pqakxbktaiiga gu apiuwrqvahm cvv df wbltr ewfuuuqgc iv amvggaltd. Hwj by qef eatb, A lau xsgtkkmaattq ergwururqws wkbz ihg bjxcm wx ihg ugsen. Bzpt K zwbeojwg dkaujsuqfv wkbz ihg Uwsieid Bap, ezdm K uwi op Njxdcg si tjm Dxnpif. We uias hg pss sgmf p skuaaat bzxni il Iydqfvep, ifs lcqv ropaasetitae ubjtsu wf ihg jddwkvy duv wx ihg kscdnm. Tjt jwo ihg bjxcm esh dqvw we ewmad pwl txrtsxn. Um zu testen, ob du den richtigen Schlüssel gefunden hast, führe mit dem Schlüssel, den du überprüfen willst, eine Vigenère-Entschschlüsselung für den folgenden Text durch und gib den resultierenden Klartext in das folgende Formular ein: UPANOQOZDNIIAZAGSSTHGKZXEVPWTCJI

Das Geburtstagsparadoxon & Kollisionsresistente Hashfunktionen

Aufgaben

In der Kryptographie zeigen wir oftmals, dass die Erfolgswahrscheinlichkeit eines optimalen Angreifers vernachlässigbar gering ist. Das Berechnen von Wahrscheinlichkeiten kann sehr unintuitiv sein. Ein beliebtes Beispiel für ein oftmals unintuitives Ergebnis ist die Antwort auf die folgende Frage: Was ist die Wahrscheinlichkeit, dass 2 beliebige Personen in einer Gruppe von 23 zufällig gewählten Personen am gleichen Tag im Jahr (Schaltjahre ausgeschlossen) Geburtstag haben (unter der Annahme, dass jeder Geburtstag gleich wahrscheinlich ist)?
2 aus 23 Personen haben mit einer Wahrscheinlichkeit von 2 * (1-(364/365)22) am gleichen Tag im Jahr Geburtstag.
Von den 23 Personen haben 2 Personen mit Wahrscheinlichkeit 23*(1/365 * 1/364) am gleichen Tag im Jahr Geburtstag.
Die Wahrscheinlichkeit, dass 2 der 23 Personen am gleichen Tag im Jahr Geburtstag haben, beträgt 1-(365 * 364 * .. * 343)/36523.
Von den 23 Personen haben 2 Personen mit Wahrscheinlichkeit 22/365 am gleichen Tag im Jahr Geburtstag.
Mit einer Wahrscheinlichkeit von 2/23 haben 2aus 23 Personen am gleichen Tag im Jahr Geburtstag.
2 aus 23 Personen haben mit einer Wahrscheinlichkeit von 23 * (1-(364/365)22) am gleichen Tag im Jahr Geburtstag.

Eine Hashfunktion H ist ein Programm, welches eine Nachricht m von beliebiger Länge auf eine Prüfsumme (engl. Hash) von fester Länge abbildet, notiert als H(m). Obwohl es nicht möglich ist, Nachrichten beliebiger Länge auf eindeutige Prüfsummen von fester Länge abzubilden, wird von Hashfunktionen gefordert, dass die Prüfsummen möglichst eindeutig in dem Sinne sind, dass es schwierig ist, zwei verschiedene Nachrichten zu berechnen, die dieselbe Prüfsumme haben. Zwei Nachrichten m,m' mit der gleichen Prüfsumme (d.h. H(m) = H(m')) werden als Kollision bezeichnet. In der Praxis wird von Hashfunktionen, die für Prüfsummen benutzt werden, Kollisionsresistenz gefordert: Das heißt, dass kein realistischer Angreifer in der Lage ist Kollisionen zu berechnen.

In dem Geburtstagsparadoxon lässt sich folgende Geburtstagshashfunktion G finden: Jede Person wird auf ihren Geburtstag im Jahr abbildet. Damit ist das Geburtstagsdatum (ohne die Jahreszahl) bei dieser Geburtstagshashfunktion G die Prüfsumme. Die obige Frage lässt sich damit folgendermaßen uminterpretieren: Was ist die Wahrscheinlichkeit, dass es bei der Geburtstagshashfunktion eine Kollision in einer Gruppe von 23 zufällig gewählten Personen gibt? Für jede Hashfunktion, mit 365 möglichen Prüfsummen, ist die Wahrscheinlichkeit für eine Kollisionen mindestens genauso hoch wie für diese Geburtstagshashfunktion.

In der Praxis ist man an der Fragestellung interessiert, wie hoch für eine gegebene Hashfunktion H, die Wahrscheinlichkeit für eine Kollision in einer großen Menge von Nachrichten ist. Nach dem Geburtstagsparadoxon gibt es für jede Hashfunktion H schon in eine Menge von zufällig gewählten Nachrichten mit signifikanter Wahrscheinlichkeit eine Kollision.

Gegeben sei eine Hashfunktion H, eine Nachricht m beliebiger Länge auf eine Prüfsumme von 10 Bit abbildet. Mit maximal welcher Wahrscheinlichkeit befindet sich in einer Menge von 400 zufällig gewählten Nachrichten eine Kollision für diese Hashfunktion? Falls es mehrere richtige Antworten gibt, wähle bitte die Kleinste dieser oberen Schranken aus. (Tipp: Mit 10 Bit können 210=1024 mögliche Prüfsummen dargestellt werden. Zum Vergleich: Mit 9 Bit können 29=512 mögliche Prüfsummen dargestellt werden. Mit 9 Bit können also alle Geburtstage dargestellt werden.)
Eine Kollision tritt höchstens mit einer Wahrscheinlichkeit von 2 * (1-(1023/1024)399)auf.
In den 400 Nachrichten gibt es mit Wahrscheinlichkeit 400*(1/1024 * 1/1023)eine Kollision.
Die Wahrscheinlichkeit, dass es eine Kollision in den 400 Nachrichten gibt, beträgt höchstens 1-(1024 * 1023 * .. * 625)/(1024400).
In den 400 Nachrichten gibt es höchstens mit Wahrscheinlichkeit 399/1024 eine Kollision.
Mit einer Wahrscheinlichkeit von höchstens 2/400 gibt es in einer Menge von 400 Nachrichten eine Kollision.
Eine Kollision gibt es mit einer Wahrscheinlichkeit von maximal 400 * (1-(1023/1024)399).

In einigen Anwendungen genügt es, wenn die Hashfunktion H eine schwächere Eigenschaft erfüllt: schwache Kollisionsresistenz. Dabei wird lediglich gefordert, dass es für eine gegebene Prüfsumme t schwierig ist, eine Nachricht m zu finden, die diese Prüfsumme hat: H(m) = t. Eine Hashfunktion H, die Kollisionsresistenz ist, ist auch schwach kollisionsresistent, weil ein Angreifer, der schwache Kollisionsresistenz brechen kann, benutzt werden kann, um Kollisionsresistenz zu brechen, in dem man einfach eine Nachricht m wählt, deren Prüfsumme H(m) berechnet und das Ergebnis t := H(m) dem Angreifer gegen schwache Kollisionsresistenz weiterleitet, welcher dann eine weitere Nachricht m' mit der gleichen Prüfsumme ausgibt: H(m') = t = H(m). Wenn es also keinen Angreifer gegen Kollisionsresistenz gibt, kann es auch keinen Angreifer gegen schwache Kollisionsresistenz geben.

Sicheres Passwortprüfen

Jeder Online-Dienst, der eine Registrierung mit einem Benutzernamen und einem Passwort fordert, muss nach der Registrierung sicher prüfen können, ob ein bei der Anmeldung eingegebenes Passwort korrekt ist. Ein Online-Dienst muss also hinreichend viel vom Passwort speichern, um prüfen zu können, ob das bei der Anmeldung eingegebene Passwort mit dem bei der Registrierung benutzten Passwort übereinstimmt. In den letzten Jahren wurde vermehrt von Einbrüchen in die Systeme großer Dienste, wie etwa Yahoo oder Adobe, berichtet. Würden also Passwörter von einem Dienst im Klartext gespeichert werden, könnte ein Einbrecher diese Passwörter stehlen und auch bei anderen Diensten verwenden. Somit haben Online-Dienste eine Verantwortung, für den Falle eines Einbruchs, möglichst wenig Information über das Passwort eines Benutzers zu speichern. Optimalerweise sollte das System des Dienstes nicht mehr Information über ein Passwort speichern als notwendig ist, um zu überprüfen, ob ein eingegebenes Passwort valide ist. In der Praxis werden hierfür verschiedene Techniken benutzt.

Eine gängige Methode zum Prüfen eines Passwortes pw bei der Anmeldung ist das Speichern einer Prüfsumme H(pw) des Passwortes mittels einer geeigneten Hashfunktion H. In der vorherigen Aufgabe haben wir Kollisionsresistenz und schwache Kollisionsresistenzvon Hashfunktion beschrieben. Zum Speichern von Passwörtern genügt allerdings Kollisionsresistenz nicht; Kollisionsresistenz schließt nicht aus, dass ein Angreifer alleine durch die Prüfsumme t eine Nachricht m'berechnen kann, die diese Prüfsumme hat: H(m') = t. Man fordert daher zusätzlich, dass die Hashfunktion H schwer zu invertieren ist. Genauer: Für eine gegebene Prüfsumme H(m)einer zufällig gewählten Nachricht m findet kein realistischer Angreifer, der nur die Prüfsumme H(m) kennt, eine Nachricht m', welche genau diese Prüfsumme hat: H(m') = H(m). Eine Funktion H, die diese Eigenschaft hat, nennt man Einwegfunktion (engl. "One-Way Function"). Wir nehmen im Folgendem an, dass die benutzte Hashfunktion H sowohl kollisionsresistent als auch eine Einwegfunktion ist. Für die folgenden Aufgaben nennen wir solche Hashfunktionen sicher und die von ihnen ausgegebenen Prüfsummen nennen wir ebenfalls sicher.

Methode 1: Eine Prüfsumme des Passwortes speichern

Bei dieser Methode speichert der Dienst eine sichere Prüfsumme H(pw)des Passwortes pw zusammen mit dem Benutzernamen. Bei der Eingabe des Passwortes wird genau dann die Anmeldung als erfolgreich gewertet, wenn die Prüfsumme H(pw') des eingegebenen Passwortes pw mit der gespeicherten Prüfsumme übereinstimmt: H(pw') = H(pw).

Methode 2: Eine Prüfsumme des Passwortes mit Salz speichern

Bei dieser Methode zieht der Dienst zuerst eine Zufallszahl s (Salz genannt) von 128 Bit Länge, d.h. eine Zahl zwischen 0 und 2128-1. Diese Zahl s hängt der Dienst dann an das Passwort pw an (wir notieren die zusammengesetzte Nachricht als pw+s). Für diese modifizierte Nachricht pw+s berechnet der Dienst eine sichere Prüfsumme H(pw+s) und speichert H(pw+s)zusammen mit dem Salz s und dem Benutzernamen. Bei der Eingabe eines Passwortes pw' prüft der Dienst dann, ob die gespeicherte Prüfsumme H(pw+s) mit der Prüfsumme H(pw'+s) übereinstimmt. Falls dies der Fall ist, wird die Anmeldung als erfolgreich bewertet.

Methode 3: Eine Prüfsumme des Passwortes mit Salz und Pfeffer speichern

Bei dieser Methode wird zusätzlich zu dem zufällig gezogenen Salz eine weitere, kleinere Zufallszahl p (Pfeffer oder geheimes Salz genannt) von 10 Bit Länge gezogen, also eine Zahl zwischen 0 und 1023. Der Dienst speichert dann bei der Registrierung H(pw+s+p) zusammen mit dem Salz s und dem Benutzernamen, aber ohne den Pfeffer p. Bei der Anmeldung prüft der Dienst dann für das eingegebene Passwort pw' und für jede Zahl p' zwischen 0 und 1023, ob die gespeicherte Prüfsumme H(pw+s+p) mit der Prüfsumme H(pw'+s+p') übereinstimmt. Falls dies für ein p' der Fall ist, wird die Anmeldung als erfolgreich bewertet.

Ein bekannter Angriff auf Passwörter ist ein Wörterbuchangriff. Die meisten Personen wählen Passwörter, die echte Wörter oder Teile echter Wörter beinhalten. Der Sprachexperte Wolfgang Klein zählte in einer Untersuchung etwa 5,3 Millionen Wörter in der deutschen Sprache.

Viele Passwörter sind aus normalen Wörtern zusammengesetzt. Man nimmt an, dass Hochleistungsrechner problemlos 260 Möglichkeiten in kürzester Zeit durchprobieren können. Selbst gute Heimrechner können mittels massiver Parallelisierung auf Grafikkarten in kurzer Zeit mehr als 240 Möglichkeiten in kürzester Zeit durchprobieren.

Realistische Angreifer können 5.300.000, also weniger als 223, Möglichkeiten problemlos ausprobieren. Da die meisten Menschen geschätzt einen Wortschatz von lediglich 70.000, also weniger als 217 , Wörtern haben, können realistische Angreifer in kurzer Zeit sogar die häufigsten Kombinationen aus Wörtern und anderen Daten, wie z.B. Namen und Geburtstagen, ausprobieren.

Um den Angriff noch effizienter zu gestalten, kann ein Angreifer vorab eine Datenbank mit allen möglichen Passwörtern und den entsprechenden Prüfsummen erstellen (siehe Methode 1 bis 3). Nach einem erfolgreichen Einbruch in einen Online-Dienst kann er nun vergleichen, welche Prüfsummen beim Online-Dienst gespeichert waren, die ebenfalls in seiner vorausberechneten Tabellen enthalten waren. Durch die Vorausberechnung kann ein solcher Angriff um ein Vielfaches beschleunigt werden.

Aufgaben

Welche der folgenden Aussagen sind richtig? (Mehrfachnennung ist möglich.)

Methode 3 schützt besser gegen den erweiterten Wörterbuchangriff als Methode 2.
Methode 2 schützt besser gegen den erweiterten Wörterbuchangriff als Methode 1.
Betrachten wir folgendes Szenario: (i) ein Angreifer hat im Zuge eines Angriffs die gesamte gehashte Passwortliste eines Dienstes kopieren können, (ii) die Passwörter sind derart, dass der Angreifer alle Passwörter mittels normaler Wörterbuchangriffe nicht schneller als in zwei Tagen knacken kann, und (iii) die Passwörter sind nur ein halbes Jahr gültig, weil die Benutzer dieses Dienstes ihre Passwörter halbjährlich ändern müssen, daher kann der Angreifer die Passwörter nur noch in den nächsten 6 Monaten verkaufen.

In diesem Szenario schützt Methode 3 besser dagegen, dass ein Angreifer alle Passwörter knacken und gewinnbringend einsetzen kann, als Methode 2.
Methode 2 schützt besser gegen einen normalen Wörterbuchangriff auf ein einzelnes Passwort als Methode 1.