Some thoughts about cryptanalysis
Later this year I will have text published in the Nordic Yearbook on Law Informatics (Nordisk Årsbok i Rättsinformatik): "A Paradigm Shift in Electronic Surveillance Law".
I wrote a section about cryptanalysis but later came to the conclusion that the section should be excluded. Considering that the work is done I do not want it to be vasted. After participating in a discussion on Rick Falkvinge's blog which, inter alia, concerned cryptanalysis I decided to publish the section here. It is written for a law journal which explains why it is quite rudimentary. The purpose of this section was to explain why law enforcement and intelligence agencies focus more on traffic analysis and less on content analysis. My explanation is that there is a tendency that with increasing processing power of computers the efficiency between encryption and attacking a crypto (cryptanalysis) is growing, to the detriment of the later. Thus, traffic analysis is becoming more important.
All comments are welcome. Please have some understanding that I am lawyer and not a mathematician.
Encryption and Cryptanalysis
With increasing processing power of computers the efficiency between encryption and attacking a crypto (cryptanalysis) is growing, to the detriment of the later.1) I will use the example of the RSA algorithm to explain why there is such a tendency. The RSA is an algorithm used for public-key cryptography and it was invented by Ronald L. Rivest, Adi Shamir, and Leonard Adleman in 1977, the letters RSA are the initials of their surnames. The RSA cryptosystem is based on the use of prime numbers and factoring.2)
Prime numbers are numbers that are not evenly divisible by any smaller number, except 1, for example 2, 3, 5, 7, 11, and 13. A non-prime, or composite number, is the product of smaller primes, known as its prime factors. 391, for example is the product of the primes 17 and 23. A number is factored when all of its prime factors are identified. As the size of the composite number increases, the difficulty of factoring and cryptanalysis increases rapidly.3) I will explain why.
RSA involves a public key for encryption and a private key for decryption. The private key corresponds to the public key, because both are based on the same modulus, n, which in turn is based on prime numbers.4) In the example above n is 391. One method of cryptanalysis is for attacker to discover the private key corresponding to a given public key. This is done by factoring the public modulus, n, into its prime factors, in the example above 17 and 23. From the prime factors and the public key exponent e, the attacker can easily get the private key exponent d. The difficulty lies in factoring n. The encryptor can use larger prime factors increasing the difficulty to factor.5) As indicated above, increasing processing power of computers allows the use of larger prime factors which will increase the difference in efficiency between encryption and cryptanalysis, to the detriment of the later.
The resources needed to add a digit when encrypting is linear while the resources needed to attack such a crypto a crypto is exponential. See the chart below.6)
However, there is a danger that an attacker in the future may use faster machines and better factoring algorithms than are currently available, which may be used to attack RSA cryptosystem keys generated in the past.7) Moreover, I am making a general observation which does not exclude the possibility that specific encryption techniques already may be subject to successful attacks that use currently available technology and algorithms.
It is easy to factor 100-digit numbers with today's hardware and algorithms. There is no public information which indicates that numbers of more than 200 digits have been successfully factored. For example, RSA modulus RSA-2048, has a length of 2048 bits (617 decimal digits). RSA laboratories expect RSA-2048 to stand for decades, assuming that there will be no fundamental algorithmic or computing advances.8) Such advances may include the discovery of a new factoring method which factoring researchers consider has a remote possibility, or the development of a quantum computer which involves significant practical difficulties.9)
1) FRA, 14 March 2007, Sveriges Television (Publ.), Frågor & svar, (16 November 2008), Question & Answer 5; Klamberg, Mark, Nilsson, Mikael, Petersson, Anna, Seipel, Peter, Flyghed, Janne, Magnusson Sjöberg, Cecilia, Karlgren, Jussi, Bylund, Markus, Palmås, Karl, Ström, Pär, Thorburn, Daniel & Westerholm, Johan, FRA-lagen medför massiv kartläggning av oskyldiga Dagens Nyheter, 3 September 2008
2) RSA Laboratories (Publ.), RSA Algorithm, "http://www.rsa.com/rsalabs/node.asp?id=2146", (27 November 2008)
3) RSA Laboratories (Publ.), The RSA Factoring Challenge FAQ, "http://www.rsa.com/rsalabs/node.asp?id=2094#HowWereTheNumbersGenerated", (27 November 2008)
4) RSA Laboratories (Publ.), Crypto FAQ, "http://www.rsa.com/rsalabs/node.asp?id=2152", (27 November 2008), section 3.1.1 What is the RSA cryptosystem?
5) ibid, section 3.1.3 What would it take to break the RSA cryptosystem?; section 2.3.3 What is the factoring problem?
6) I have made the following assumptions concerning the relation between resources (y) and digits used (x) with k as the potential combinations for a digit. In the example with the entry code to the house there is 10 potential combinations (0-9). This generates the following to functions. Resources to encrypt (y1)=x*10; resources to attack (y2)=e x
7) ibid, section 2.3.5 What improvements are likely in factoring capability?
8) The RSA Factoring Challenge FAQ
9) Crypto FAQ, section 2.3.3 What is the factoring problem?; section 2.3.5 What improvements are likely in factoring capability?; section 2.4.3 What is exhaustive key search?; section 7.17 What is quantum computing?
5 kommentarer:
Du utgår ju från att det inte finns några fler metoder att använda asymmetrisk kryptografi. Elliptisk kurv-kryptografi (ECC) har inte den egenskapen att kryptonycklarnas storlek ökar snabbare än säkerheten i kryptot. Eller, med andra ord att de två kurvorna i ditt diagram hade varit parallella med varandra, om du jämfört ECC-kryptografi med kostnaden att bryta kryptot, snarare än att bara fokusera på det gamla RSA-kryptot.
Alltså är det inget problem.
Faktiskt är det inte ens ett problem om kvantdatorer skulle visa sig gå att tillverka. Först och främst såras inte symmetriska krypton speciellt mycket, deras effektiva nyckellägd halveras bara, vilket inte är så farligt ur ett komplexitetsanalysperspektiv, O(n) är nästan ekvialent med O(2n). Eller på normalt språk: AES256 blir lika säkert som AES128, om det attackeras av en kvantdator. Och 128-bitars symmetriska blockkrypton går ändå inte att knäcka idag. Vid sidan av att symmetriska krypton inte skadas, så är myten om att all form av asymmetrisk kryptografi skulle gå att knäcka bara man hade tillgång till kvantdatorer bara en myt. McEliece är ett exempel på ett sådant kryptosystem.
Så, vi är safe :)
xor,
Jag uppfattar ändå att din slutsats är den samma, det har blivit svårare att forcera kryptoskydd och det lär inte bli enklare även om den som vill forcera kryptot skulle få tag på en fungerande kvantdator (som de flesta menar inte finns).
xor: det är ju naturligvis vad The Man _vill få dig_ att tro
@Mark Klamberg: Ja :) Det är ju faktiskt väldigt trevligt att det är så.
Några, mer eller mindre matematiskt pedantiska, synpunkter:
i. Först och främst vänder jag mig mot att du framställer det (åtminstone uppfattar jag det så) som att det är utvecklingen av hårdvara som gör att kryptoanalys blir allt svårare. Visserligen är det korrekt att förhållandet mellan kostnaden att dekryptera och att kryptera ökar när vår förmåga till numerisk beräkning ökar; men detta är förhållandevis banalt.
[Ditt påstående att detta förhållande är exponentiellt är i själva falskt; redan den naiva testa-tills-du-hittar-en-faktor-metoden terminerar på en tid exponentiell i roten ur n (för att faktorisera n räcker det - uppenbarligen - att leta upp till sqrt(n), men detta tillhör de matematiska petitesserna. För det av xor nämnda(*) ECC-systemet är våra bästa dekrypteringsalgoritmer exponentiella i storleken av nyckeln, jag bortser därför från denna petitess i det återstående.]
Det relevanta är i själva verket förhållandet (i fallet med RSA) mellan våra bästa algoritmer för faktorisering (dekryptering) och för att identifiera primtal (detta är den besvärliga delen i genererandet av nycklarna, den är inte linjär i nyckelstorleken, som påstås i din postning).
På grund av detta förhållande är det alltid möjligt att välja en tillräckligt stor nyckel - dvs så stor att även ett enormt beräkningskluster skulle ta miljontals år (säg) för att knäcka krypteringen - att ytterligare öka storleken på nycklarna (bara för att förbättrade processorer har gjort det möjligt) vore dock relativt meningslöst (ett krypto som inte kan knäckas på 10^12 år är inte särskilt mycket intressantare än ett som inte kan knäckas på 10^6).
Alltså: alltsedan upptäckten av public key cryptography i början av 70-talet har effektiv kryptoanalys av dessa protokoll varit omöjlig (förutsatt förstås att man bemödar sig om att välja lämpliga nycklar), något som alltså är synnerligen oberoende av (den enorma) utvecklingen i processorkraft.
ii. Pga de matematiska petitesserna ovan är analogin med kodlåset missvisande (men kanske inte på något egentligen allvarligt sätt).
iii. Den slutsats du vill dra, med avseende på de juridiska frågor som intresserar dig, är förstås korrekt: moderna framsteg inom kryptografi och datorteknik har gjort kryptoanalys praktiskt omöjlig (och det kan vi förvänta oss att den fortsätter att vara för många, många decennier; varken effektiva faktoriseringsalgoritmer eller kvantdatorer är någonting vi ens kan se vid horisonten).
iv. Av i-iii drar jag slutsatsen att beslutet att stryka texten ovan från årsboken var korrekt: de tekniska bitarna är dels inte korrekta i detaljer (vilket de bör vara i en akademisk publikation, matematisk oder nicht), dels bidrar de inte på något väsentligt sätt till att belysa de juridiska frågorna.
(*) Det mesta xor hade att säga om ECC är dock uppåt väggarna fel;
1. Det första påståendet om kryptonycklarnas storlek är falskt redan i ljuset av det lilla jag sagt ovan.
2. Hela texten handlar ju om asymmetriska (public key) krypton, varför i herrans namn komma dragade med symmetriska?? (Dessa är knappast särskilt relevanta för de juridiska frågor du vill diskutera.)
Skicka en kommentar