Criptoanálisis

El criptoanálisis (del grec kryptós, ‘amagat’, i analýein, ‘desnugar’) és una branca de la criptología dedicada a l'estudi dels sistemes criptogràfics en l'objectiu d'identificar les seues debilitats i quebrantar la seua seguritat sense dispondre de l'informació secreta associada. En un us no tècnic, la pràctica sol denominar-se «trencar» o «forçar» un còdic, encara que estos térmens posseïxen significats específics dins de l'argot de la disciplina. Les persones que es dediquen al criptoanálisis es denominen criptoanalistas.

Els métodos i tècniques del criptoanálisis han canviat dràsticament a través de l'història de la criptografia, adaptant-se a una creixent complexitat criptográfica. Els sistemes criptogràfics han evolucionat des dels métodos de llapis i paper del passat, passant per màquines com Enigma, utilisada pels nazis durant la Segona Guerra Mundial, fins a aplegar als sistemes basats en computadores del present. En aumentar la potència de càlcul dels sistemes criptogràfics, també els esquemes criptogràfics han anat fent-se més complexos. A mitan dels anys 1970 es va inventar una nova classe de criptografia: la criptografia asimètrica. Els métodos utilisats per a trencar estos sistemes són per lo general radicalment diferents dels anteriors, i usualment impliquen resoldre un problema cuidadosadament construït en el domini de la matemàtica pura. L'eixemple més conegut és la factorisació de sancers.

Els resultats del criptoanálisis han canviat també: ya no és possible tindre un èxit illimitat en trencar un còdic, i existix una classificació jeràrquica de lo que constituïx un atac en la pràctica.

Objectiu

La Lorenz-SZ42-2 va ser la màquina de sifrat utilisada per l'eixèrcit alemà durant la Segona Guerra Mundial.

L'objectiu del criptoanálisis és trobar debilitats en els sistemes criptogràfics que permeten elaborar atacs criptoanalíticos que trenquen la seua seguritat sense el coneiximent d'informació secreta. Per a això estudia en profunditat el disseny i propietats dels sistemes criptogràfics.

En un sistema criptográfico de sifrat, per eixemple, un estudi criptoanalítico pot consistir en conseguir la clau secreta o simplement en accedir al text en clar sense siquiera tindre dita clau. No obstant, el criptoanálisis no solament s'ocupa dels sifrats, sino que el seu àmbit és més general: estudia els sistemes criptogràfics en l'objectiu de sortejar la seguritat d'atres tipos d'algoritmes i protocols criptogràfics.

No obstant, el criptoanálisis sol excloure els atacs que no tenen com a objectiu primari els punts dèbils de la criptografia utilisada, com els basats en el soborn, la coerció física, el robo o el keylogging. Estos atacs representen un risc creixent per a la seguritat informàtica, i en la pràctica solen resultar més efectius que el criptoanálisis tradicional per a vulnerar un sistema.

Àmbits d'estudi

Per a la consecució del seu objectiu, d'elaboració d'atacs criptoanalíticos que 'trenquen' la seguritat dels sistemes criptogràfics, els criptoanalistas estudien els sistemes criptogràfics en l'objectiu de descobrir debilitats que es puguen aprofitar. Per a això estudien els sistemes des de distints enfocaments.

Teoria de l'informació

La teoria de l'informació proporciona ferramentes per a evaluar la seguritat dels sistemes criptogràfics. Per eixemple, en els sistemes de sifrat s'estudia l'entropía de la clau, dels criptogrames i dels mensages en clar. Com el mensage en clar sol estar expressat en idiomes humans, també és interessant l'estudi del seu entropía i en especial la seua ràtio d'entropía.

Els criptoanalistas també estudien el secret dels sistemes criptogràfics. Per eixemple, en els sistemes de sifrat estudien el grau de secret caracterisant aquells sistemes que tenen secret perfecte a nivell teòric. Del seu estudi es conclou que el secret perfecte requerix que el número de claus siga a lo manco tan gran com el número de mensages. Açò és impracticable llevat para els cridats cifradores de llibreta d'un sol us. En la pràctica la major part dels sistemes tenen claus finitas. Per a caracterisar la seguritat d'estos sistemes els criptoanalistas han desenrollat el concepte de distància d'unicitat, que és el valor mínim de caràcters sifrats que fan que solament hi haja una clau possible que haja segut utilisada per a obtindre este criptograma. Per a això s'aprofita el concepte de l'entropía condicional del coneiximent de la clau una volta conegut el text sifrat.

Per a un sistema de sifrat hi ha una série d'entropía condicionals interessants:

Supongam:

• Un mensage $M_1$ és somés a un procés de sifrat usant la clau $K_1$, obtenint $E(K_1,M_1)=C_1$.
• $P_C(K)$ representa la provabilitat condicional de la clau K donat el criptograma rebut $C$. A voltes també es denota per $P(K|C)$.
• $P_C(M)$ representa la provabilitat condicional del mensage $M$ dau el criptograma rebut $C$. A voltes també es denota per $P(M|C)$.

Llavors:

• Podem medir l'incertitut (l'entropía) del coneiximent de la clau una volta conegut el text sifrat, i per tant medir la equivocació de la clau, $H_C(K)$, també denotada per $H(K|C)$, per mig de la fòrmula:

La primera igualtat és per la definició de l'entropía condicional i la segona per aplicació del teorema de Bayes.

Observar que si $H_C(K)=0$ significa que es podrà trencar el sifrat, puix ya no hi ha incertitut. Esta anulació nos introduïx en el concepte de distància d'unicitat.

• Podem medir l'incertitut (l'entropía) del coneiximent del mensage una volta conegut el text sifrat, i per tant medir la equivocació del mensage, $H_C(M)$, també denotada per $H(M|C)$, per mig de la fòrmula:

La primera igualtat és per la definició de l'entropía condicional i la segona per aplicació del teorema de Bayes.

• Podem medir l'incertitut (l'entropía) del coneiximent de la clau una volta conegut el text sifrat i el mensage en clar, i per tant medir la equivocació de l'aspecte de la clau, $H_{C,M}(K)$, també denotada per $H(K|M,C)$, per mig de la fòrmula:

• Podem medir l'incertitut (l'entropía) del coneiximent del mensage una volta conegut el text sifrat i la clau, denotat per $H_{C,K}(M)$ o per $H(M|K,C)$. Donada una clau, la relació entre text sifrat i text en clar és un a un i, per tant, $H_{C,K}(M)=0$.

S'ha demostrat que es complix la següent relació entre les distintes entropía:

D'esta relació podem traure una conclusió:

L'objectiu de qualsevol que use un cifrador és tindre un valor de $H_{C,M}(K)$ alt per a que el sistema tinga la màxima fortalea possible en cas que l'atacant disponga tant del text sifrat com del text clar (atac en text clar conegut). No obstant, per l'expressió de l'equació, per a això és necessari que $H_C(M)$ siga menut. Tindre un valor chicotet de $H_C(M)$ implica que hi haja poca incertitut respecte al text clar una volta conegut el text sifrat (atac en sol text sifrat disponible), lo que és contrari als interessos de qualsevol que sifre un mensage. Per tant, és necessària una solució de compromís per a que el sistema tinga una fortalea acceptable front a abdós tipos d'atac.

Base matemàtica i potència de càlcul

Per eixemple, la criptografia asimètrica ampra problemes matemàtics "durs" com a base per a la seua seguritat, aixina que un punt obvi d'atac és desenrollar métodos per a resoldre el problema. Els algoritmes asimètrics es dissenyen entorn a la conjeturada dificultat de resoldre certs problemes matemàtics. Si es troba un algoritme millorat que pot resoldre el problema, el criptosistema es veu debilitat. Eixemples:

• La seguritat del protocol Diffie-Hellman depén de la dificultat de calcular un logaritme discret. En 1983, Don Coppersmith va trobar una manera més ràpida de calcular logaritmes discrets (dins de certs grups), i per tant va obligar als criptógrafos a utilisar grups més grans, o diferents tipos de grups.
• La seguritat del protocol RSA depén parcialment de la dificultat en la factorisació de sancers. Per tant, un alvanç en la factorisació tindria un impacte clar en la seguritat de RSA. En 1980, es podia factorizar un número de 50 dígits en un cost de $10^{12}$ operacions elementals de computació. Per a 1984, la tecnologia en algoritmes de factorización havia alvançat fins al punt de que es podia factorizar un número de 75 dígits en les mateixes $10^{12}$ operacions. Els alvanços en la tecnologia de computació també han provocat que estes operacions es puguen realisar en un temps molt menor. La Llei de Moore predigues empíricamente que les velocitats de computació continuaran aumentant. Les tècniques de factorización podrien mostrar un desenroll paregut, pero en gran provabilitat dependran de la capacitat i la creativitat dels matemàtics, cap de les quals ha segut mai satisfactòriament predible. Números de 150 sifres, com els utilisats en RSA, han segut factorizados. L'esforç va ser major que el mencionat anteriorment, pero no estava fora dels llímits raonables per a un ordenador modern. Al començ de el XXI, els números de 150 sifres ya no es consideren suficientment grans com a clau per a RSA. Números de varis centenars de dígits se seguien considerant massa difícils de factorizar en 2005, encara que els métodos provablement continuaran millorant en el temps, obligant als tamanys de clau a mantindre el ritme de creiximent o a desenrollar nous algoritmes.

Una atra característica distintiva dels algoritmes asimètrics és que, a diferència dels atacs sobre criptosistemas simètrics, qualsevol criptoanálisis té l'oportunitat d'usar el coneiximent obtingut de la clau pública.

Bibliografia

• Helen Fouché Gaines, "Cryptanalysis", 1939, Dover. ISBN 0-486-20097-3
• Abraham Sinkov, Elementary Cryptanalysis: A Mathematical Approach, Mathematical Association of America, 1966. ISBN 0-88385-622-0
• Ibraham A. "Al-Kindi: The origins of cryptology: The Arab contributions", Cryptologia, 16(2) (April 1992) pp. 97–126.
• David Kahn, "The Codebreakers - The Story of Secret Writing", 1967. ISBN 0-684-83130-9
• Lars R. Knudsen: Contemporary Block Ciphers. Lectures on Data Security 1998: 105-126

• Bruce Schneier, "Self-Study Course in Block Cipher Cryptanalysis", Cryptologia, 24(1) (January 2000), pp. 18–34.
• Friedrich L. Bauer: "Decrypted Secrets". Springer 2002. ISBN 3-540-42674-4
• Friedman, William F., Military Cryptanalysis, Part I, ISBN 0-89412-044-1
• Friedman, William F. Military Cryptanalysis, Part II, ISBN 0-89412-064-6
• Friedman, William F. Military Cryptanalysis, Part III, Simpler Varieties of Aperiodic Substitution Systems, ISBN 0-89412-196-0
• Friedman, William F. Military Cryptanalysis, Part IV, Transposition and Fractionating Systems, ISBN 0-89412-198-7
• Friedman, William F. i Lambros D. Callimahos, Military Cryptanalytics, Part I, Volume I, ISBN 0-89412-073-5
• Friedman, William F. i Lambros D. Callimahos, Military Cryptanalytics, Part I, Volume II, ISBN 0-89412-074-3
• Friedman, William F. i Lambros D. Callimahos, Military Cryptanalytics, Part II, Volume I, ISBN 0-89412-075-1
• Friedman, William F. i Lambros D. Callimahos, Military Cryptanalytics, Part II, Volume II, ISBN 0-89412-076-X