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
Matematik, kryptologi och bevisbar säkerhet » Kryptoblog

Matematik, kryptologi och bevisbar säkerhet

September 16th, 2007 by Joachim Strömbergson Leave a reply »

Neal Koblitz, som förutom att han åkt tåg i Peru är professor i matematik vid University of Washington:
Neal Koblitz

Neal har skrivit en tankeväckande och läsvärd artikel publicerad i senaste numret av American Mathematical Society Notices, kallad The Uneasy Relationship Between Mathematics and Cryptography om förhållandet mellan matematik och kryptologi samt varför han inte tror på begreppet bevisbar säkerhet.

Jag är inte kryptolog, och (kan jag erkänna) har aldrig känt mig helt komfortabel och naturligt hemma i matematikens magiska och fantastiska värld. För mig är det därför fascinerande att läsa en artikel av en person som tittar på kryptologi från det motsatta hållet (om man kan kalla det det).

Neal Koblitz börjar med en kort bakgrund till sitt engagemang inom kryptologin och hur han som matematiker var med och publicerade dom första rönen vad gäller att använda olika typer av kurvor (exempelvis elliptic curve) för att skapa assymetriska krypton. Men huvudelen av artikeln är fokuserad på matematikers och kryptologers olika bakgrund, hur man förhåller sig till sin forskning samt vad som egentligen är ett bevis.

En skillnad mellan kryptologi och matematik som Neal tar upp är hur resultat publiceras:


In 1996 I was the program chair of Crypto. To someone trained in mathematics this was an unsettling experience. About two-thirds of the submissions arrived by courier mail within 48 hours of the final deadline. Many had obviously been rushed and were full of typesetting errors. One author had sent me only the odd-numbered pages. A few had violated the requirement of anonymity (there was a policy of double-blind reviews). Several had disregarded the guidelines that had been sent to them.
And in many cases the papers had little originality; they were tiny improvements over something the same authors had published the year before or a minor modification of someone else’s work.

Mathematical publishing works differently. In the first place, most articles appear in journals, not conference proceedings—and journals don’t have deadlines. In the second place, people in mathematics tend to have a low opinion of authors who rush into print a large number of small articles—the derogatory term is LPU (least publish- able unit)—rather than waiting until they are ready to publish a complete treatment of the subject in a single article.

Mathematicians, who are part of a rich tradition going back thousands of years, perceive the passing of time as an elephant does. In the grand scheme of things it is of little consequence whether their big paper appears this year or next. Computer science and cryptography, on the other hand, are influenced by the corporate world of high technology, with its frenetic rush to be the first to bring some new gadget to market. Cryptographers, thus see time passing as a hummingbird does. Top researchers expect that practically every conference should include one or more quickie papers by them or their students.

Neal Koblitz verkar alltså anse att kryptologin som en del av datavetenskap skyndar med sina resultat, och detta syns inte minst på de bevis som används. Koblitz skriver:


The idea of “provable security” is to give a mathematically rigorous proof of a type of conditional guarantee of the security of a cryptographic protocol. It is conditional in that it typically has the form “our protocol is immune from an attack of type X provided that the mathematical problem Y is computationally hard.

The form that proofs of security take is what is known as a reduction. Reductions from one problem to another occur implicitly throughout mathematics; in computer science, reductions are the main tool used to compare and classify problems according to their difficulty.

In provable security papers the authors try to prove that a mathematical problem that is widely believed to be computationally hard, such as factoring large integers or finding elliptic curve discrete logs, reduces to a successful attack of a prescribed type on their cryptographic protocol.

Och vad är då kruxet? Jo ett stort krux som Koblitz pekar på är att även om de problem som man försöker reducera sitt säkerhetsproblem till är asymptotiskt svåra, innebär det inte att säkerhetsproblemen är säkra i de data/nyckelstorlekar som används praktiskt:


What had happened was that people had made recommendations for parameter values that were based on an asymptotic theorem. That theorem said that in the limit as N​ approaches infinity, you can securely generate O (log​log​N​) pseudorandom
bits each time you perform a squaring modulo the composite number N​. (Here “securely” means, roughly speaking, that no one can distinguish between the sequence and a truly random one by an algorithm that runs in reasonable time.) However, as I mentioned when discussing Joe Silverman’s xedni calculus, it is fallacious to use an asymptotic result as a practical guarantee of security. Rather, one needs to perform a detailed analysis using realistic ranges for the parameters.

Koblitz tar som exempel upp problemet med OAEP och den förbättring som Krawczyk publicerade 2005.

Jag kan som sagt för lite för att bedöma om Koblitz har rätt eller ej, men jag tycker att hans artikel är läsvärd och inte så lite småskrämmande. Koblitz ser ut att få stöd av iaf James A. Donald som på maillistan Cryptography postade följande tanke:


If a proof is a record of a mental journey in which one person has discovered an important truth, and then made a record of that journey adequate so that a second person can walk the same path and see the same truth, then cryptography could do with more and better proofs.

If, on the other hand, a proof is an argument impressively decorated with mathematical sounding jargon, cryptography could do with a good deal fewer of them.

Vad tror du?

No related posts.

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

Advertisement

4 comments

  1. Mikael says:

    Problemet med artikeln av Neal Koblitz är just att den så lätt kan övertala personer som inte är insatta i vad det hela handlar om.

    För det första: skillnaden i publiceringsmodell finns, och man kan argumentara både för och emot den. Det är dock inte det som är det centrala i artikeln.

    För det andra: Koblitz argumenterar mot att forskare inom krypto bevisar olika säkerhetsegenskaper, en minst sagt märklig ståndpunkt för en matematiker. Argumentet verkar vara att han a) inte förstår vad det är som bevisas och att b) felaktiga bevis har publicerats.

    Det exempel som Koblitz tar upp är ganska så missvisande, IMHO. För en mer insatt genomgång, se Krawczyk’s svar: http://www.ee.technion.ac.il/~hugo/ams-letter/

  2. Tomas says:

    Hur insatt är du själv? Klart man inte kan bevisa säkerheten hos en algoritm med ett ändligt antal steg med en asymptotisk sats, ej heller med olika svaga reduktioner… Han säger att krypto inte behöver fler pseudobevis, till skillnad från riktiga matematiska bevis.

  3. Mikael says:

    @Tomas: Jag gissar att din kommentar var riktad till mig.

    Jag är måttligt insatt, till den grad att jag gärna läser (och förstår) den typen av bevis som Koblitz attackerar.

    De bevis som presenteras är inte “pseudobevis”, det är “riktigt matematiska bevis”. Det intressanta är att man just kan reducera frågan om hur bra ett protokoll är mot en viss typ av attackerare, till vilken komplexitetsklass av problem det är ekvivalent med.

    Som ett bra exempel kan man ta RSA och Rabin. RSA kan knäckas om man kan lösa heltalsfaktorisering, och likaså för Rabin. Men det omvända gäller inte för båda. Om vi kan knäcka RSA betyder det inte att heltasfaktorisering är lätt, eller att Rabin är lätt. Däremot så betyder en knäckning av Rabin att både RSA och heltalsfaktorisering är lätt.

    Att välja parametrar till en algoritm är alltid något annat än asymptotiska argument, men samtidigt bör man låta sig guidas av dessa resultat, för de ger en insikt om hur systemet beter sig.

    Koblitz argumenterar också för att det inte är intressant att skydda sig genom att reducera till ett problem som vi inte har en stark undre-gräns för. Men då kan man lika gärna kasta ut en stor del av datalogin, som ofta börjar med mantrat “vi antar att P!=NP”.

Leave a Reply

You must be logged in to post a comment.