Thema: Diverses zum RSA-Kryptosystem

[SiLæncer]

Eine Arbeitsgruppe des BSI hat die mit 20.000 US-Dollar dotierte Challenge RSA-640 mit Hilfe der Methode General Number Field Sieve (GNFS) gelöst. Die Forscher benötigten für die Zerlegung der Zahl mit 193 Dezimalstellen in ihre beiden 320 Bit langen Primfaktoren rund fünf Monate Rechenzeit auf einem Opteron-Cluster mit 80 2,2-GHz-Prozessoren, wie der Website Crypto-World zu entnehmen ist. Das Team konnte bereits im Mai dieses Jahres die Faktorisierung von RSA-200 abschließen und war ebenfalls im Dezember 2003 an der bisher größten gelösten Challenge RSA-576 beteiligt.

Wer das Ergebnis beispielsweise mit dem GNU Arbitrary Precision Calculator verifizieren möchte, die Zahlen für RSA-640 lauten:

310 7418240490 0437213507 5003588856 7930037346 0228427275 4572016194 8823206440 5180815045 5634682967 1723286782 4379162728 3803341547 1073108501 9195485290 0733772482 2783525742 3864540146 9173660247 7652346609 = 1634733 6458092538 4844313388 3865090859 8417836700 3309231218 1110852389 3331001045 0815121211 8167511579 * 1900871 2816648221 1312685157 3935413975 4718967899 6851549366 6638539088 0271038021 0449895719 1261465571

Die RSA-Laboratorien schreiben ihre Challenges schon seit Anfang der 90er-Jahre aus. Die nächst größere Challenge ist nun die mit 30.000 US-Dollar dotierte RSA-704. Wer sich schon an RSA-1024 oder RSA-2048 versuchen möchte – schließlich benötigt man im günstigsten Fall mit einer gehörigen Portion Glück nur einige wenige Divisionsversuche – kann sich auf 100.000 bzw. 200.000 US-Dollar Preisgeld freuen.

Die Schwierigkeit der Zerlegung großer Zahlen in ihre Primfaktoren ist das Fundament der meisten aktuell eingesetzten kryptographischen Verfahren. 35=5*7 lässt sich noch leicht im Kopf rechnen. Doch schon bei 81072007=9001*9007 dürfte dies selbst mit einem guten Taschenrechner problematisch werden. Bei entsprechend größeren Zahlen scheitern schnell selbst die größten heute verfügbaren Rechensysteme. Schließlich steigt der Zeitaufwand für eine Faktorisierung exponentiell mit der Stellenzahl: Für eine zusätzliche Stelle ist der Aufwand um einen gewissen Faktor X größer, für zwei Stellen schon X*X, für drei X*X*X usw.

Somit ist es zwar nach aktuellem Stand der Wissenschaft bis zur erfolgreichen Faktorisierung von 1024 Bit langen Zahlen, wie sie noch bis in die späten 90er-Jahre für PGP-Keys und SSL-Zertifikate eingesetzt wurden, noch ein langer Weg, da der Zeitaufwand für eine Faktorisierung exponentiell mit der Zahl der Bits ansteigt. Doch berücksichtigt man das ebenfalls exponentielle Wachstum der Rechenleistung, rückt die Faktorisierung von RSA-1024 schon zumindest in absehbare Nähe.

Bisher geht man davon aus, dass sich das Faktorisierungsploblem nur mit exponentiellem Aufwand lösen lässt. Dass es keinesfalls doch mit polynomialem, also wesentlich geringerem Aufwand zu lösen wäre, konnte bisher aber nicht bewiesen werden. Es ist deshalb nicht auszuschließen, dass grundlegende Durchbrüche in der Zahlentheorie zu weiteren drastischen Verkürzungen im Zeitaufwand führen werden. Und die in Zukunft wahrscheinlich anstehende Verfügbarkeit von Quantencomputern, die solche Faktorisierungsprobleme theoretisch im Handumdrehen lösen können, setzt den heutigen gängigen Verfahren ein jähes Ende.

Nach der schrittweisen Heraufsetzung der verwendeten Schlüssellängen hilft dann nur noch ein Umschwenken in der zu Grunde liegenden Mathematik. Man kann das RSA-Verfahren leicht dahingehend modifizieren, dass es nicht mehr auf den üblichen Zahlenringen, sondern auf so genannten Elliptischen Kurven operiert. Auf diesen ist das Faktorisierungsproblem ungleich schwieriger zu lösen. Ein Vorteil der Elliptic-Curve-Crytography, kurz ECC, ist die wesentlich kürzere Schlüssellänge. Ein ECC-Schlüssel mit nur 256 Bit ist nach heutigem Ermessen etwa so sicher wie ein normaler RSA-Schlüssel mit 3072 Bit.

Siehe dazu auch:

    * All Hackers Need To Know About Elliptic Curve Cryptography, Phrack #63

Quelle und Links : http://www.heise.de/security/news/meldung/65957

[SiLæncer]

Die RSA Security Inc. hat die Ergebnisse einer Befragung von 601 Geschäftsleuten und 603 Konsumenten auf der RSA-Konferenz unter dem Titel Internet Confidence Index Shows That - for Businesses and Consumers - Transactions are Outpacing Trust vorgestellt. Die Ergebnisse unterscheiden sich gravierend zwischen Geschäftsleuten und Privatanwendern sowie zwischen den USA und Europa, berichten US-Medien.

Die Gründe für die Kluften sind vielfältig. So fühlen sich die Menschen in Unternehmen sicherer, da sie dort durch Firewalls und andere Defensivmaßnahmen geschützt sind, während Heimbenutzer meist nur durch eine Software-Firewall und einen Virenscanner geschützt werden.

62 Prozent der US-Unternehmen konnten in den vergangenen zwölf Monaten Umsatzsteigerungen mit Online-Transaktionen beobachten, während in Frankreich und England nur 49 Prozent Mehreinnahmen durch Internet-Geschäfte erzielten. In Deutschland sehen die Zahlen düsterer aus, hier haben nur 34 Prozent der befragten Unternehmen ihren Umsatz steigern können; 52 Prozent schätzen das Ergebnis auf einen konstanten Umsatz. Das Ergebnis spiegelt auch die wahrgenommene Sicherheit der Unternehmen wider. Während 86 Prozent der amerikanischen, britischen und französischen Unternehmen ihre Online-Handel als ziemlich, sehr oder extrem sicher einstuften, taten dies deutsche Unternehmen nur zu 64 Prozent.

Dem steht entgegen, das 67 Prozent der US-Unternehmen um die Verletzlichkeit ihrer Netzwerke oder um betrügerischen Informationszugriff sorgen, während in Europa nur 37 Prozent um die Netzwerksicherheit bangen. Die amerikanischen Verbraucher sorgen sich auch mehr um die Sicherheit ihrer persönlichen Daten in den Unternehmen; da in Europa der Datenschutz jedoch in Gesetze mit engen Grenzen gegossen ist, verwundert dieses Ergebnis nicht. Hier spielt auch herein, dass betrügerische E-Mails (Phishing) größtenteils auf amerikanische Nutzer ausgerichtet ist. In Frankreich und Deutschland können nur zwei Drittel der Nutzer etwas mit dem Begriff Identitätsdiebstahl anfangen, während amerikanische Bürger zu 90 Prozent um diese Gefahren wissen.

Wer für den Datenschutz zuständig ist, sehen Geschäftsleute und Verbraucher ebenfalls von Land zu Land unterschiedlich. Konsumenten suchen die Verantwortung ganz klar bei den Online-Händlern und Banken. Die amerikanischen und englischen Banken und Unternehmen sehen die Verantwortung aber nur zu 26 Prozent bei sich selbst. In Deutschland stimmt die Wahrnehmung und Umsetzung präzise mit dem Verbraucherdenken überein, während Banken und Geschäfte in Frankreich den schwarzen Peter der geschützten Datenkommunikation und Transaktionen lieber dritten Parteien zuschustern wollen.

Die Ergebnisse der Umfrage legen nahe, dass Unternehmen und Banken noch an ihren Sicherheitsinfrastrukturen und der Anwenderkommunikation feilen müssen. Wenn ein Unternehmen sich selbst nicht als sicher einschätzt, kann es das von einem potenziellen Kunden auch nicht erwarten.

Quelle und Links : http://www.heise.de/security/news/meldung/69637

[SiLæncer]

Wissenschaftler haben eine 768 Bit lange Zahl mit 232 Dezimalstellen in ihre beiden Primfaktoren zerlegt. Die Ergebnisse veröffentlichten sie in einem Artikel. Bei der Zahl handelt es sich um die im Rahmen der RSA Challenge als RSA-768 veröffentlichte Ziffernfolge. RSA-Verschlüsselung mit 768 Bit langen Schlüsseln muss somit fortan als geknackt gelten.

Das Team mit Mitgliedern aus der Schweiz, Japan, Deutschland, Frankreich, den USA und den Niederlanden benöigte für die Faktorisierung rund zweieinhalb Jahre. Mit dem ersten Rechenschritt, der Polynomial Selection, war ein Cluster aus 80 PCs ein halbes Jahr lang beschäftigt. Der zweite und wesentlich aufwändigere Schritt, das Sieving, dauerte etwa zwei Jahre auf einem Cluster aus mehreren hundert Rechnern. Laut den Wissenschaftlern wäre ein einzelner Opteron-Prozessor mit 2 GByte RAM rund 1500 Jahre mit dem Sieben beschäftigt gewesen.

Weil RSA-512 vor rund einem Jahrzehnt geknackt wurde, gehen die Forscher davon aus, dass die Rechenleistung zum Bewältigen von RSA-1024 in rund zehn Jahren zur Verfügung stehen dürfte. Ihre Empfehlung lautet daher, alle RSA-Schlüssel mit 1024 Bit bis spätestens 2014 aus dem Verkehr zu ziehen.

Quelle : www.heise.de

[SiLæncer]

Forscher der University of Michigan konnten durch Manipulation der Spannungsversorgung eines Embedded-Prozessors an den von ihm verwendeten geheimen RSA-Schlüssel gelangen. Der Angriff zielt auf die Berechnung von RSA-Signaturen mit Hilfe des FWE-Algorithmus (Fixed Window Exponentiation), wie es beispielsweise in der Kryptobibliothek OpenSSL der Fall ist. Bei dem untersuchten Embedded-Prozessor handelt es sich um ein SPARC-basiertes Leon3-SoC, das auf einem FPGA von Xilinx läuft und laut den Wissenschaftlern aber repräsentativ für Embedded-Systeme sein soll.

Grundlage der von Andrea Pellegrini, Valeria Bertacco und Todd Austin in einem Paper beschriebenen Attacke ist die Absenkung der Spannungsversorgung der Prozessoreinheit gerade so weit, dass es bei den zur Signaturberechnung erforderlichen Multiplikationsoperationen gelegentlich zu Bitfehlern kommt. Aufgrund der mathematischen Eigenschaften des FWE-Algorithmus lassen sich aus einer fehlerhaften Unterschrift unter gewissen Umständen vier Bits des geheimen Schlüssels errechnen. Da man nicht vorhersagen kann, welche Unterschriften einen geeigneten Fehler enthalten und welche vier Schlüsselbits sich daraus berechnen lassen, muss man sehr viele Signaturen sammeln.

Zur Rekonstruktion des geheimen Schlüssels aus einem Satz von 8800  fehlerhaften Signaturen benötigte ein Cluster aus 80 PCs rund 100 Stunden. Laut einem Bericht von The Register, der den Kryptoexperten Karsten Nohl zitiert, lässt sich der FWE-Algorithmus leicht mit einer Fehlererkennung ausstatten, die die Attacke vereitelt. Die OpenSSL-Entwickler wollen demnach in Kürze auch einen entsprechenden Patch liefern.

Der Angriff dürfte sich jedoch in der Praxis nur schwer umsetzen lassen. Laut den Forschern muss man an rund 1000 Signaturen gelangen, bei deren Berechnung es im FWE-Algorithmus zu einer fehlerhaften Multiplikation mit genau einem gekippten Bit gekommen ist. Selbst in dem speziellen Testsystem der Forscher, das mit fast nichts anderem als der Signaturerzeugung beschäftigt war, war dies nur bei 10 Prozent der Unterschriften der Fall.

In der Praxis dürften sich auch nur wenige Produktivsysteme dazu bringen lassen, beständig Signaturen zu erzeugen, die sich vom Angreifer auch noch ohne weiteres auslesen lassen. Ist der Prozessor hauptsächlich mit anderen Dingen beschäftigt, kommt es durch die Spannungsmanipulation vorwiegend zu Fehlern und gegebenenfalls Abstürzen in Programmcode außerhalb des RSA-Codes.

Darüber hinaus sind RSA-basierte Kryptosysteme im Embedded-Bereich nur selten anzutreffen, etwa bei HDMI/HDCP oder in TPM-Modulen, die in der Regel jedoch in speziellen Chips implementiert sind. Wie gut sich der FWE-Angriff auf andere Prozessoren und Kryptosysteme übertragen lässt, wird sich noch zeigen müssen. In vielen Szenarien dürfte es auch – beispielsweise mit einer Cold-Boot-Attacke – wesentlich leichter sein, an die geheimen Schlüssel zu gelangen.

Siehe dazu auch:

    * Fault-Based Attack of RSA Authentication, wissenschaftliches Paper zum Angriff


Quelle : www.heise.de

[ritschibie]

Ein Team aus europäischen und US-amerikanischen Mathematikern und Kryptographie-Experten entdeckte kürzlich eine Schwäche im verbreiteten Verschlüsselungs-Verfahren RSA. Ein kleiner Teil der generierten Schlüssel weist offenbar mathematische Schwächen auf, die eine Entschlüsselung der damit verschlüsselten Nachrichten durch Unbefugte ermöglichen.

Bei der sogenannten Public-Key-Kryptographie, zu der auch RSA gehört, hat jeder Benutzer zwei Schlüssel. Der eine, der sogenannte öffentliche Schlüssel, dient der Verschlüsselung von Nachrichten. Der zweite, private Schlüssel wird zum Entschlüsseln der verschlüsselten Nachrichten verwendet. RSA wird beispielsweise zum Absichern sensibler Internet-Transaktionen (Shopping, Online-Banking und ähnliches) sowie für die Verschlüsselung von Chat-Systemen und E-Mails verwendet.

Da die öffentlichen Schlüssel sich in vielen Fällen im Internet befinden, um der betreffenden Person verschlüsselte Daten schicken zu können, konnten die Forscher diese analysieren. Dabei stellten sie fest, dass es in einer "kleinen, aber messbaren Anzahl von Fällen" ein Problem mit den Schlüsseln gibt. Verursacht offenbar durch ein Problem bei der Generierung der für die Schlüssel-Erstellung benötigten Pseudo-Zufallszahlen gibt es einige Schlüssel, die Unbefugten erlauben, die verschlüsselten Daten auszulesen. Die Wissenschaftler, die ihre Forschungsergebnisse am vergangenen Dienstag in einem wissenschaftlichen Paper veröffentlichten, befürchten, dass diese Problematik - trotz der eher geringen Anzahl von Fällen - das Vertrauen der Nutzer in die RSA-Verschlüsselung nachhaltig schwächen könnte. Es gibt keine Möglichkeit für normale Nutzer, festzustellen, ob ihr Schlüssel von dem Problem betroffen ist.

Die Forscher untersuchten insgesamt gut sieben Millionen öffentliche RSA-Schlüssel. Dabei seien sie über fast 27.000 Schlüssel, die keine angemessene Sicherheit bieten, "gestolpert", berichten die Experten. Das entspricht knapp 0,4% der Schlüssel beziehungsweise vier von 1000 generierten Schlüsseln - ein geringer Prozentsatz, aber angesichts der Verbreitung des Systems dennoch eine erhebliche Anzahl Betroffener. Jeder, der "sich die Mühe macht, unsere Arbeit zu reproduzieren", könnte in diesen Fällen die privaten Schlüssel der Betroffenen rekonstruieren, schreiben die Krypto-Experten. Zwar deutet dies auf einen äußerst eingeschränkten Kreis potentieller Angreifer hin - diese müssten nicht nur über erhebliche mathematische Fähigkeiten verfügen, sondern auch einiges an Ressourcen investieren - es gibt aber durchaus Fälle, in denen ein derartiger Angriff denkbar wäre.

Die genauen Gründe für das teilweise Versagen des Pseudozufallszahlen-Generators sind derzeit noch unbekannt. Die Wissenschaftler konnten lediglich ausschließen, dass es sich um ein reines Implementierungs-Problem einer bestimmten RSA-Umsetzung handelt: das Problem tauche in "mehr als der Arbeit eines einzelnen Software-Entwicklers" auf, heißt es in dem Forschungsbericht.

Die Forscher betonen, dass es durchaus im Bereich des Möglichen sei, dass schon vor ihrer Arbeit jemand - womöglich Personen mit bösartigen Zielen - diese Schwächen aufgedeckt habe. Ihre Erkenntnisse seien nicht sonderlich anspruchsvoll, weswegen es schwer zu glauben sei, dass diese Erkenntnisse vollkommen neu seien. Insbesondere "Geheimdienste und andere Gruppen, die für ihre Neugier in diesen Dingen bekannt sind", seien wahrscheinlich schon früher auf diese Angriffsmöglichkeit gekommen, so die Einschätzung der Experten.

Die Kryptologen bemühten sich, alle Betroffenen über das Problem in Kenntnis zu setzen. Dies gestalte sich allerdings äußerst schwierig angesichts des Ausmaßes der Probleme und der dezentralen Infrastruktur, erklärten sie. Sie hätten sich trotzdem für die Veröffentlichung ihrer Forschungsergebnisse entschieden. Dies sei allerdings eine Ermessensentscheidung gewesen.

Quelle : www.gulli.com

[SiLæncer]

Ein vor Kurzem von Wissenschaftlern dokumentiertes Problem mit einer kleinen Anzahl von RSA-Schlüsseln beschränkt sich aktuellen Untersuchungen zufolge auf die Schlüssel von Netzwerk-Hardware. SSL-Zertifikate auf Websites sollen demnach nicht betroffen sein, da dort ein anderer Pseudozufallszahlen-Generator zum Einsatz kommt.

Wissenschaftler hatten kürzlich festgestellt, dass ein geringer Anteil generierter öffentlicher Schlüssel für den asymmetrischen Verschlüsselungs-Algorithmus RSA aufgrund einer Schwäche des verwendeten Pseudozufallszahlen-Generators keine sichere Verschlüsselung von Nachrichten ermöglicht. Nun kamen jedoch RSA ebenso wie die unabhängigen Kryptographie-Experten Zakir Durumeric, Eric Wustrow, Alex Halderman und Nadia Heninger zu dem Schluss, dass dieses Problem lediglich bei den Schlüsseln von Netzwerk-Geräten auftaucht. Website-Zertifikate sollen nicht betroffen sein.

Die zweite Forschergruppe widerspricht somit Befürchtungen, dass Online-Shopping-Anwendungen durch das Problem gefährdet sein könnten. Das Problem inkorrekt generierter Schlüssel betreffe "vor allem verschiedene Arten eingebetteter Geräte wie Router und VPN-Geräte, nicht vollwertige Webserver", berichten die Forscher. Allerdings seien von dem Problem anscheinend alle oder fast alle großen Hersteller betroffen. Es könne sein, dass "die ganze Geräteklasse" dieses Problem aufweise, schreiben die Forscher. Es sei bereits bekannt gewesen, dass Geräte wie Router und Firewalls Entropie-Probleme hätten. Das Ausmaß dieser Probleme sei allerdings überraschend.

Die Wissenschaftler schlussfolgern: "Dies ist ein Problem, aber es ist nichts, über das sich der Durchschnittsnutzer im Moment Gedanken machen müsste. Allerdings kommt auf die Hersteller eingebetteter Geräte viel Arbeit zu und einige System-Administratoren sollten besorgt sein. Dies ist ein Weckruf an die Sicherheits-Gemeinde und eine Erinnerung, dass sich Sicherheitsprobleme manchmal an ganz offensichtlichen Stellen verstecken."

Ihre Forschungsergebnisse wollen die Experten auch in einem wissenschaftlichen Paper präsentieren. Mit dessen Veröffentlichung planen sie allerdings zu warten, bis alle betroffenen Hersteller über das Problem informiert wurden und die Möglichkeit hatten, dieses anzugehen. Außerdem wollen die Wissenschaftler eine Website erstellen, auf der sich testen lässt, ob das eigene Gerät einen verwundbaren Schlüssel verwendet.

Quelle : www.gulli.com