Warning: Missing argument 2 for wpdb::prepare(), called in /home/stromber/public_html/kryptoblog/wp-content/plugins/wp-super-edit/wp-super-edit.core.class.php on line 109 and defined in /home/stromber/public_html/kryptoblog/wp-includes/wp-db.php on line 1222
Kubattacker mot kryptografiska funktioner » Kryptoblog

Kubattacker mot kryptografiska funktioner

September 15th, 2008 by Joachim Strömbergson Leave a reply »

En av de mest uppmärksammade händelserna på den för ungefär en månad sedan avslutade Crypto-konferensen var en presentation av Adi Shamir om en ny typ av attackmetod mot kryptografiska metoder kallad kubattack.

Adi Shamir
Adi Shamir

När metoden presenterades fanns inget om den nya metoden publicerat. Detta ledde till en hel del diskussioner och spekulationer på maillistor. Exempelvis diskuterades det mycket om krypton som AES, Twofish är sårbara.

David Wagner skrev ett par längre inlägg på Cryptography-listan (inlägg ett, inlägg två). David skrev bland annat:


Basically the method focuses on terms of the polynomial in which only one secret bit of the key appears, and many of the non-secret bits. Using chosen (or lucky) plaintexts, vary all but one of the non-secret bits, and sum the output bits (mod 2, that is, XOR).

Fix the other non-secret bit to 1. Now all the terms that involve less than the full complement of non-secret bits will appear an even number of times in the sum, and because it is mod 2, they will all cancel out! The only terms that will be left are the ones with one secret bit, and all ones for the non-secret bits… but that is linear in the secret bit! So what you are left with is a simple, linear, polynomial relating unknown (key) bits.

Nu har artikeln Cube Attacks on Tweakable Black Box Polynomials av Itai Dinur and Adi Shamir publicerats på IACR. Författarna skriver i artikelns (långa) sammanfattning:


Almost any cryptographic scheme can be described by tweakable polynomials over GF (2), which contain both secret variables (e.g., key bits) and public variables (e.g., plaintext bits or IV bits). The cryptanalyst is allowed to tweak the polynomials by choosing arbitrary values for the public variables, and his goal is to solve the resultant system of polynomial equations in terms of their common secret variables.

In this paper we develop a new technique (called a cube attack) for solving such tweakable polynomials, which is a major improvement over several previously published attacks of the same type.

For example, on the stream cipher Trivium with a reduced number of initialization rounds, the best previous attack (due to Fischer, Khazaei, and Meier) requires a barely practical complexity of 2**55 to attack 672 initialization rounds, whereas a cube attack can find the complete key of the same variant in 2**19 bit operations (which take less than a second on a single PC). Trivium with 735 initialization rounds (which could not be attacked by any previous technique) can now be broken with 2**30 bit operations, and by extrapolating our experimentally verified complexities for various sizes, we have reasons to believe that cube attacks will remain faster than exhaustive search even for 1024 initialization rounds.

Whereas previous attacks were heuristic, had to be adapted to each cryptosystem, had no general complexity bounds, and were not expected to succeed on random looking polynomials, cube attacks are provably successful when applied to random polynomials of degree d over n secret variables whenever the number m of public variables exceeds d + logd n. Their complexity is 2d−1 n + n2 bit operations,
which is polynomial in n and amazingly low when d is small.

Cube attacks can be applied to any block cipher, stream cipher, or MAC which is provided as a black box (even when nothing is known about its internal structure) as long as at least one output bit can be represented by (an unknown) polynomial of relatively low degree in the secret and public variables. In particular, they can be easily and automatically combined with any type of side channel attack that leaks some partial information about the early stages of the encryption process (which can typically be
represented by a very low degree polynomial), such as the Hamming weight of a byte written into a register.

Publiceringen av artikeln har skapat nya diskussioner, exempelvis på Bruce Schneiers blog.

Min uppfattning om Adi Shamir är att han är en av världens absolut bästa kryptologer, risken att han skulle missat fullständigt och metoden inte alls fungerar tror jag är liten. Men jag kan villigt erkänna att jag kan för lite krypanalys för att göra en vettig bedömning av den nya metoden.

Om det Itai Dinur och Adi Shamir skriver stämmer borde detta vara ett stort steg framåt för kryptanalysen. Och lackmustestet kommer antagligen att vara om det dyker upp en ny våg av attacker mot olika specifika funktioner så fungerar kubattacken.

Att Trivium, en av de nyligen utsedda algoritmerna i eSTREAM-portföljen (och lite av en personlig favorit) skulle få problem så här nära efter avslutningen av eSTREAM visar hur en ny metod plötsligt kan kullkasta flera år av analysarbete.

Vi kommer med stor sannolikhet att få återkomma till den här nya attackmetoden. Inte minst under AHS-tävlingen kommer kubattacken antagligen att uppmärksammas.

No related posts.

Related posts brought to you by Yet Another Related Posts Plugin.

Advertisement

6 comments

  1. albert says:

    Spännande att den här attacken fungerar mot Trivium. Jag undrar vad den här attacken innebär för de mest använda blockchiffren, som DES, 3DES, AES, Blowfish osv. Det är verkligen en spännande fråga.

    Låt säga att den skulle minska antalet försök som behövs att knäcka till exempel DES och 3DES så att det skulle gå att göra det på en vanlig PC. Det skulle innebära att alla bankdosor över en natt skulle bli osäkra, och det är bara en av följderna…

  2. Phallos7 says:

    Det här är väl lite OT iof men jag behöver lite råd inför den väntande FRA-lagen och ställer följande frågor:

    1. Är PGP Knäckt?

    2. Är detta program sämre?

    http://www.darksoftware.narod.ru/narod_is_best/darkcrypt-gui.zip

    Den som gjort programmet rekommenderar:

    “Rijndael, Twofish – very strong algorithms. For puplic key encryption you can use RSA-Rijndael, RSA-Twofish, etc. algorithms.”

    Är det leksaker när man har med FRA att göra? Är PGP bättre? Själv kan jag inte ett dyft om kryptering så jag vore tacksam för råd och om du har tid:

    Testa programmet!

  3. blackadder says:

    1. Nej, PGP är inte knäckt.

    2. Varken AES eller Twofish påverkas av “kubattackerna”.

    Känner inte till DarkCrypt och det är svårt att få reda på något – länken går till en Rysk site… Är det open source eller är koden stängd? Kostar det pengar? Vem har kontrollerat programkoden? Hur vanligt är det? Helt enkelt – hur kan du veta att det är säkert?

    Vad gäller FRA så är det främst trafikdata som de är intresserade av. Först om du flaggas som “misstänkt” kommer de läsa din data. Kryptering skyddar inte trafikdatan utan du behöver använda anonymiserade nät typ TOR eller Freenet för att skydda dig.

    Vad gäller kryptering så är det mycket osannolikt att FRA kan knäcka någon modern algoritm. De kan gissa lösenord men inte mycket mer.

  4. Aloha!

    Bra svar Blackadder. Jag skrev följande nedan tidigare i dag och stämmer nog rätt väl med det du skriver.

    Välkommen till Kryptoblog Phallos7. Vi tar dina frågor i tur och ordning, men först en liten brasklapp: Jag är en glad kryptonördamatör och mina åsikter behöver inte alls stämma med verkligheten.

    Frågan om PGP är knäckt går inte att svara enkelt på, och det beror på att PGP är flera saker. PGP är dels en öppen standard för säker kommunikation kallad OpenPGP (http://tools.ietf.org/html/rfc4880).

    PGP är även ett specifikt program som dock har kommit i ett antal versioner och har en brokig historia. Programmet PGP är egentligen ett ramverk där kryptofunktionerna utgörs av olika algpritmer ocgh har över tiden byggt på olika algoritmer. Några algoritmer som tidigare använts, exempelvis det symmetriska kryptot Bassomatic, är osäkra.

    I dag är algoritmerna i PGP olika standardiserade algoritmer, exempelvis RSA, ElGamal, DSA, AES, CAST, IDEA.

    Dessutom är inte PGP den enda implementationen av OpenPGP, utan det finns andra implementationer exempelvis GnuPG.

    Så din fråga om PGP kan formuleras som:

    (1) Är OpenPGP knäckt?. Nej. Det är inte ett perfekt protokoll, men protokollet som sådant är bra.

    (2) Är PGP som program knäckt? Nej. Det har funnits brister i olika versioner genom åren, men PGP som applikation faller inte samman för det. Och notera att det finns andra OpenPGP-applikationer. Alla har sina vårtor, men varken PGP eller GnuPG är generellt sett osäkra att använda.

    (3) Är algoritmerna i PGP knäckta. Nej inte generellt. Vissa av algoritmerna har kända svagheter, och alla algoritmer kräver omtanke i hur de används. Men PGP, GnuPG etc hjälper dig och ser till att du inte skjuter dig i foten utan att ha varnat dig ordentligt innan.

    Vad gäller verktyget Darkcrypt har jag aldrig hört talas om verktyget förut. Jag Googlade lite men hittade inga recensioner, kommentarer eller granskningar av Darkcrypt.

    Länken går till en Windowsbinär på en rysk sida tillhörande några jag inte känner igen. Jag greppade lite på strängarna i programmet och såg en del strängar som rörde funktioner i Windows jag inte är säker på att ett krypteringsprogram har någon nytta av och skall pilla på. Kort sagt fick jag dåliga vibbar av Darkcrypt, tror inte att jag tänker testa Darkcrypt och skulle inte rekommendera någon att göra det.

    Även om jag gillar teknisk utveckling på IT-säkerhetsområdet och är svag för nya, blänkande leksaker håller jag mig till kända, väl spridda och använda befintliga program och bibliotek som PGP, OpenPGP, Truecrypt, OpenSSH och OpenSSL så mycket som möjligt. Finns det öppen källkod och dessutom granskningar och utvärderingar är det ännu bättre. Jag tror på kryptokonservatism – skall man vara kryptoparanoid skall man vara det hela tiden och även vara misstänksam mot de verktyg man använder.

    När det gäller din sista fråga om FRA och kryptosäkerhet. Med risk att orsaka dagens skratt på Lovön skulle jag våga påstå att FRAs kryptologer och kodknäckare, oavsett vilka fräcka maskiner de nu har, troligen inte kan forcera AES-256 (Rijndael är den algoritm som blev AES. Twofish är en av de andra AES-kandidaterna) på ”rimlig tid”. Samma sak gäller troligen RSA och ElGamal med ordentliga nyckellängder. Den springande punkten här är ”rimlig tid”.

    Tar vi AES som exempel finns det i dag inga öppet kända attackmetoder som knäcker AES-128 på snabbare sätt än många många år. Kan FRAs superhjärnor ha klurat ut bättre metoder? Kanske, men så mycket bättre metoder att det går på enstaka år, månader, veckor, dagar eller till och med på några minuter?

    Om vi antar att FRA klarar att forcera ett AES-128-krypterat meddelande på 10 år och informationen om var jag gömt min ovärderliga samling av Ben & Jerry-glass är värdelös (dvs glassen är uppäten) inom tre månader är mina kalorier säkra.

    Om det jag skyddar har ett värde som är längre än så, eller om jag tror att FRA är bättre på att forcera AES bör jag skruva upp min säkerhet. Då kan jag exempelvis ta till AES-256. (Detta förutsätter att FRA inte har en metod som gör att AES som algoritm inte fallerar totalt, utan där komplexiteten vid forcering fortfarande skalar med antalet bitar i nyckeln.)

    Det som ofta glöms bort är att säkerheten sitter i nyckeln. Även om du använder det symmetriska kryptot Blowfish med 448 bitars nyckel är ditt meddelande inte speciellt väl skyddad om din nyckel är ”sigge”. Handhavandefel, tillsammans med brister i implementationer, är enligt min uppfattning det största säkerhetsproblemet vid kryptering, inte svagheter i algoritmerna. (MiFare, ROT-13 och andra riktiga leksaksalgoritmer undantagna).

    Och om du nu är riktigt orolig för FRA så är det inget som hindrar att du kastar beräkningskraft på problemet.

    Kör med RSA-nycklar på många tusen bitar, kryptera i flera lager med olika algoritmer (AES ovanpå Twofish ovanpå Salsa20 ovanpå Snow 2.0 ovanpå RSA etc….), klyv meddelandet och skicka det i olika delar, kör din (krypterade) trafik genom en onion-router som TOR, använd steganografi och göm meddelandet i bilder. Tunnla överföringen av bilden mellan dig och din motpart som en bild i WoW eller ett on-line-spel. Det finns oändligt många sätt att vara jobbig på.

    Men min rekommendation är återigen att vara konservativ. Kör med GnuPG och välj ordentliga nyckellängder för RSA och ElGamal. Använd AES-256 som blockkrypto och gärna med CTR eller GCM som kryptomod. För hashfunktioner föreslår jag SHA-2 256 eller 512. OpenSSL för kommunikation och Truecrypt för skydd av filer på system borde du kunna lita på.

    Vad säger ni andra. Var felar jag?

  5. Phallos7 says:

    Tack för svaren. Darkcrypt är en plugin (WXD) till filhanteraren Total Commander (windows). Jag funderade på att skicka krypterade meddelanden som attachment eftersom många inte kan hantera PGP. Då ville jag distribuera ett enkelt program för att dekryptera. Därför bad jag utvecklaren att göra ett simpelt gränssnitt till WXD filen (pluginen). Det blev drag an drop mm (jag har källkoden också). Det borde min farmor klara av.

    Men rådet att kryptera i flera steg köper jag direkt. Det tänkte jag faktiskt inte på.

    Kör truecrypt på mitt USB-minne också och det fungerar bra

  6. Phallos7 says:

    Rättning: WCX plugin skall det vara om darkcrypt

Leave a Reply

You must be logged in to post a comment.