Meet-in-the-middle attack (original) (raw)
Ein Meet-in-the-middle-Angriff ist ein generischer kryptographischer Angriff. Er macht sich zu Nutze, dass anfällige kryptographische Algorithmen ihren Schlüssel zerteilen, und während der Berechnung des Chiffrats in einzelnen Schritten nur einen Teil des Schlüssels verwenden. Ein gängiges Beispiel dafür sind Verschlüsselungsverfahren, die ihren eigentlichen Verschlüsselungsalgorithmus mehrfach mit jeweils unterschiedlichen Schlüsseln anwenden.
| Property | Value |
|---|---|
| dbo:abstract | L'atac per trobada a mig camí o meet-in-the-middle és un atac similar a l'atac d'aniversari, que utilitza un . Mentre que l'atac d'aniversari tracta de trobar dos valors del domini d'una funció que tenen com a imatge el mateix resultat, aquest atac tracta de trobar un valor en el rang del domini de composició de dues funcions, de tal manera que la imatge de la primera funció és igual que la imatge inversa de la segona funció - d'aquí el nom de l'atac-. Va ser desenvolupat el 1977 per Whitfield Diffie i Martin Hellman, en un intent d'expandir un bloc xifrat. En la recerca d'una millor seguretat del xifrat d'un bloc, es podria intentar la idea d'utilitzar simplement dues claus criptogràfiques per a xifrar dues vegades les dades. A priori, es podria pensar que això hauria elevar al quadrat la seguretat de l'esquema de doble xifrat. Certament, una recerca exhaustiva de totes les claus possibles requeriria intents, si cada clau fora de n bits, comparat amb els intents requerits per a una clau única. No obstant això, Diffie i Hellman van trobar un compromís entre temps i memòria que podria trencar el xifrat en només el doble de temps.L'atac es basa en el xifrat per un extrem i el desxifrat per l'altre, buscant una trobada a mig camí. Suposem que l'atacant coneix el text P i el seu xifrat C, és a dir:,on K 1 i K 2 són les dues claus. L'atacant, aleshores, pot calcular E K ( P ) per a totes les claus possibles K i guardar els resultats en memòria. Després, pot calcular D K ( C ) per a cada clau K i comparar-la amb la taula en memòria. Si arriba a una coincidència, és plausible que l'atacant hagi descobert dues claus, i pot comprovar-ho un segon parell de text original i text xifrat. Si la longitud de clau és n , aquest atac només necessita xifrats (i un espai de l'ordre de claus ), comparat amb l'atac de força bruta, el qual necessita un espai de claus a costa d'executar xifrats. (ca) Ein Meet-in-the-middle-Angriff ist ein generischer kryptographischer Angriff. Er macht sich zu Nutze, dass anfällige kryptographische Algorithmen ihren Schlüssel zerteilen, und während der Berechnung des Chiffrats in einzelnen Schritten nur einen Teil des Schlüssels verwenden. Ein gängiges Beispiel dafür sind Verschlüsselungsverfahren, die ihren eigentlichen Verschlüsselungsalgorithmus mehrfach mit jeweils unterschiedlichen Schlüsseln anwenden. (de) El ataque por encuentro a medio camino, también conocido por su término inglés meet-in-the-middle o por sus siglas en inglés MITM, consiste en aprovechar el diseño de un sistema G modelándolo como una secuencia de dos procesos A y B, en el que la salida de A será la entrada de B. El objetivo del ataque consiste en, dados los valores preestablecidos de entrada y salida E y S del sistema global G, encontrar la definición de los procesos A y B de tal forma que haya un I tal que: Expresado en lenguaje formal: Se trata de encontrar un valor en el rango del dominio de composición de dos funciones, de tal manera que la imagen de la primera función dé lo mismo que la imagen inversa de la segunda función. Por tanto para poder aplicar este ataque es necesario conocer la inversa del proceso B. La forma en la que funciona el ataque es el siguiente: Se atacan de forma independiente ambas funciones, A y B, por fuerza bruta sobre el espacio de claves obteniendo por un lado el conjunto de posibles valores de I que puede producir como valor entrada E (probando todas las claves) y por el otro lado se obtiene el conjunto de posibles valores I que pueden producir como valor de salida S (probando todas las claves). Si entre estos dos conjuntos de posible valores de I, encontramos un valor que está en ambos, entonces probablemente hayamos encontrado las claves correctas. Para verificar que las claves son las correctas habría que probar con otros valores de E y S y comprobar que los resultados coinciden. Observar que el ataque meet-in-the-middle es un claro ejemplo de algoritmo que reduce el tiempo de ejecución a costa de tener más necesidades de memoria (hay que almacenar los valores resultado de probar con todos las posibles claves del proceso A). Es una situación de compromiso espacio-tiempo. Ideado en 1977 por Whitfield Diffie y Martin Hellmanaplicado para reducir la seguridad de cifradores simétricos por bloques obtenidos a partir de 2 cifradores simétricos en bloque iguales puestos uno a continuación uno del otro, lo que se suele implementar mediante 2 rondas de cifrado. Es decir, los llamados doble cifrado (en inglés double encryption). Posteriormente este esquema se ha aplicado para atacar la seguridad de otros tipos de sistemas como las funciones hash criptográficas llamadas 'códigos de detección de modificaciones'. (es) The meet-in-the-middle attack (MITM), a known plaintext attack, is a generic space–time tradeoff cryptographic attack against encryption schemes that rely on performing multiple encryption operations in sequence. The MITM attack is the primary reason why Double DES is not used and why a Triple DES key (168-bit) can be brute-forced by an attacker with 256 space and 2112 operations. (en) L'attacco meet-in-the-middle (da non confondere con man in the middle) è un attacco crittografico che, come l'attacco del compleanno, fa uso di un compromesso costo-prestazioni. Mentre l'attacco del compleanno tenta di trovare due valori nel dominio di una funzione che si mappino sullo stesso valore nel suo codominio, l'attacco meet-in-the-middle tenta di trovare un valore in ognuno degli intervalli e domini della composizione di due funzioni tali che la mappatura di uno attraverso la prima funzione sia la stessa dell'immagine inversa dell'altra attraverso la seconda funzione - trovandosi letteralmente nel mezzo della funzione composta. (it) 中間一致攻撃（ちゅうかんいっちこうげき、英：Meet-in-the-middle attack）とは、暗号理論において誕生日攻撃と同様に時間と空間のトレードオフを利用した攻撃方法の一種である。 (ja) Meet in the middle – jest rodzajem ataku kryptograficznego z jawnym tekstem, autorstwa Merkle’a i Hellmana (1981). Do jego przeprowadzenia konieczna jest znajomość zarówno tekstu jawnego, jak i zaszyfrowanego (atak ze znanym tekstem jawnym). Algorytmami podatnymi na tego rodzaju ataki są algorytmy używające dwóch lub więcej kluczy do wielokrotnego szyfrowania tym samym algorytmem np. 3DES. (pl) 中途相遇攻擊（英語：Meet-in-the-middle attack）是密碼學上以空間換時間的一種攻擊。 (zh) В криптоанализе методом встречи посередине или атакой «встречи посередине» (англ. meet-in-the-middle attack) называется класс атак на криптографические алгоритмы, асимптотически уменьшающих время полного перебора за счет принципа «разделяй и властвуй», а также увеличения объема требуемой памяти. Впервые данный метод был предложен Уитфилдом Диффи и Мартином Хеллманом в 1977 году. (ru) У криптоаналізі методом зустрічі посередині або атакою «зустріч посередині» (англ. meet-in-the-middle attack) називається клас атак на криптографічні алгоритми, які асимптотично зменшують час повного перебору за рахунок принципу «розділяй і володарюй», а також збільшення об'єму необхідної пам'яті. Вперше цей метод був запропонований Уітфілдом Діффі і Мартіном Геллманом у 1977 році. (uk) |
| dbo:thumbnail | wiki-commons:Special:FilePath/1D_MITMNEW.png?width=300 |
| dbo:wikiPageID | 423418 (xsd:integer) |
| dbo:wikiPageLength | 16818 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1117803445 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Cryptography dbr:Cryptography_standards dbr:Triple_DES dbr:Wireless_security dbr:Data_Encryption_Standard dbr:Whitfield_Diffie dbr:GOST_(block_cipher) dbr:Space–time_tradeoff dbr:3-subset_meet-in-the-middle_attack dbc:Cryptographic_attacks dbr:Partial-matching_meet-in-the-middle_attack dbr:Birthday_attack dbr:Block_cipher dbr:Martin_Hellman dbr:Lookup_table dbr:Double_DES dbr:File:1D_MITMNEW.png dbr:File:2D_MITMNEW.png dbr:File:MD_MITMNEW.png dbr:Hummingbird-2 dbr:KTANTAN |
| dbp:date | May 2015 (en) |
| dbp:reason | No way to verify this edit: (en) |
| dbp:wikiPageUsesTemplate | dbt:About dbt:Multiple_issues dbt:Mvar dbt:Ordered_list dbt:Original_research dbt:Refimprove dbt:Reflist dbt:Short_description dbt:Tmath dbt:Unreferenced_section dbt:Verify_source dbt:Cryptography_navbox dbt:Synthesis dbt:Diff |
| dct:subject | dbc:Cryptographic_attacks |
| gold:hypernym | dbr:Attack |
| rdf:type | yago:WikicatCryptographicAttacks yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Attack100972621 yago:Event100029378 yago:Operation100955060 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity dbo:MilitaryConflict |
| rdfs:comment | Ein Meet-in-the-middle-Angriff ist ein generischer kryptographischer Angriff. Er macht sich zu Nutze, dass anfällige kryptographische Algorithmen ihren Schlüssel zerteilen, und während der Berechnung des Chiffrats in einzelnen Schritten nur einen Teil des Schlüssels verwenden. Ein gängiges Beispiel dafür sind Verschlüsselungsverfahren, die ihren eigentlichen Verschlüsselungsalgorithmus mehrfach mit jeweils unterschiedlichen Schlüsseln anwenden. (de) The meet-in-the-middle attack (MITM), a known plaintext attack, is a generic space–time tradeoff cryptographic attack against encryption schemes that rely on performing multiple encryption operations in sequence. The MITM attack is the primary reason why Double DES is not used and why a Triple DES key (168-bit) can be brute-forced by an attacker with 256 space and 2112 operations. (en) L'attacco meet-in-the-middle (da non confondere con man in the middle) è un attacco crittografico che, come l'attacco del compleanno, fa uso di un compromesso costo-prestazioni. Mentre l'attacco del compleanno tenta di trovare due valori nel dominio di una funzione che si mappino sullo stesso valore nel suo codominio, l'attacco meet-in-the-middle tenta di trovare un valore in ognuno degli intervalli e domini della composizione di due funzioni tali che la mappatura di uno attraverso la prima funzione sia la stessa dell'immagine inversa dell'altra attraverso la seconda funzione - trovandosi letteralmente nel mezzo della funzione composta. (it) 中間一致攻撃（ちゅうかんいっちこうげき、英：Meet-in-the-middle attack）とは、暗号理論において誕生日攻撃と同様に時間と空間のトレードオフを利用した攻撃方法の一種である。 (ja) Meet in the middle – jest rodzajem ataku kryptograficznego z jawnym tekstem, autorstwa Merkle’a i Hellmana (1981). Do jego przeprowadzenia konieczna jest znajomość zarówno tekstu jawnego, jak i zaszyfrowanego (atak ze znanym tekstem jawnym). Algorytmami podatnymi na tego rodzaju ataki są algorytmy używające dwóch lub więcej kluczy do wielokrotnego szyfrowania tym samym algorytmem np. 3DES. (pl) 中途相遇攻擊（英語：Meet-in-the-middle attack）是密碼學上以空間換時間的一種攻擊。 (zh) В криптоанализе методом встречи посередине или атакой «встречи посередине» (англ. meet-in-the-middle attack) называется класс атак на криптографические алгоритмы, асимптотически уменьшающих время полного перебора за счет принципа «разделяй и властвуй», а также увеличения объема требуемой памяти. Впервые данный метод был предложен Уитфилдом Диффи и Мартином Хеллманом в 1977 году. (ru) У криптоаналізі методом зустрічі посередині або атакою «зустріч посередині» (англ. meet-in-the-middle attack) називається клас атак на криптографічні алгоритми, які асимптотично зменшують час повного перебору за рахунок принципу «розділяй і володарюй», а також збільшення об'єму необхідної пам'яті. Вперше цей метод був запропонований Уітфілдом Діффі і Мартіном Геллманом у 1977 році. (uk) L'atac per trobada a mig camí o meet-in-the-middle és un atac similar a l'atac d'aniversari, que utilitza un . Mentre que l'atac d'aniversari tracta de trobar dos valors del domini d'una funció que tenen com a imatge el mateix resultat, aquest atac tracta de trobar un valor en el rang del domini de composició de dues funcions, de tal manera que la imatge de la primera funció és igual que la imatge inversa de la segona funció - d'aquí el nom de l'atac-. Suposem que l'atacant coneix el text P i el seu xifrat C, és a dir:,on K 1 i K 2 són les dues claus. (ca) El ataque por encuentro a medio camino, también conocido por su término inglés meet-in-the-middle o por sus siglas en inglés MITM, consiste en aprovechar el diseño de un sistema G modelándolo como una secuencia de dos procesos A y B, en el que la salida de A será la entrada de B. El objetivo del ataque consiste en, dados los valores preestablecidos de entrada y salida E y S del sistema global G, encontrar la definición de los procesos A y B de tal forma que haya un I tal que: (es) |
| rdfs:label | Atac Meet-in-the-middle (ca) Meet-in-the-middle-Angriff (de) Ataque Meet-in-the-middle (es) Attacco meet-in-the-middle (it) 中間一致攻撃 (ja) Meet-in-the-middle attack (en) Meet in the middle (pl) Метод встречи посередине (ru) Метод зустрічі посередині (uk) 中途相遇攻擊 (zh) |
| owl:sameAs | freebase:Meet-in-the-middle attack yago-res:Meet-in-the-middle attack wikidata:Meet-in-the-middle attack dbpedia-ca:Meet-in-the-middle attack dbpedia-de:Meet-in-the-middle attack dbpedia-es:Meet-in-the-middle attack dbpedia-fa:Meet-in-the-middle attack dbpedia-he:Meet-in-the-middle attack dbpedia-hu:Meet-in-the-middle attack dbpedia-it:Meet-in-the-middle attack dbpedia-ja:Meet-in-the-middle attack dbpedia-lmo:Meet-in-the-middle attack dbpedia-no:Meet-in-the-middle attack dbpedia-pl:Meet-in-the-middle attack dbpedia-ru:Meet-in-the-middle attack dbpedia-simple:Meet-in-the-middle attack dbpedia-tr:Meet-in-the-middle attack dbpedia-uk:Meet-in-the-middle attack dbpedia-zh:Meet-in-the-middle attack https://global.dbpedia.org/id/56DFx |
| prov:wasDerivedFrom | wikipedia-en:Meet-in-the-middle_attack?oldid=1117803445&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/1D_MITMNEW.png wiki-commons:Special:FilePath/2D_MITMNEW.png wiki-commons:Special:FilePath/MD_MITMNEW.png |
| foaf:isPrimaryTopicOf | wikipedia-en:Meet-in-the-middle_attack |
| is dbo:wikiPageDisambiguates of | dbr:MITM |
| is dbo:wikiPageRedirects of | dbr:Meet-in-the-middle dbr:Meet_in_the_middle_attack |
| is dbo:wikiPageWikiLink of | dbr:DES-X dbr:Index_of_cryptography_articles dbr:Kuznyechik dbr:SHA-2 dbr:Cryptanalysis dbr:Triple_DES dbr:Claw_finding_problem dbr:Prince_(cipher) dbr:Space–time_tradeoff dbr:3-subset_meet-in-the-middle_attack dbr:Cybersecurity_information_technology_list dbr:Partial-matching_meet-in-the-middle_attack dbr:Hill_cipher dbr:Baby-step_giant-step dbr:ARIA_(cipher) dbr:Key_whitening dbr:Biclique_attack dbr:Birthday_attack dbr:Hierocrypt dbr:Dmitry_Khovratovich dbr:CCMP_(cryptography) dbr:Cipher_security_summary dbr:Knapsack_problem dbr:MARS_(cipher) dbr:MITM dbr:Serpent_(cipher) dbr:NTRUEncrypt dbr:Outline_of_cryptography dbr:Meet-in-the-middle dbr:Meet_in_the_middle_attack |
| is owl:differentFrom of | dbr:Man-in-the-middle_attack |
| is foaf:primaryTopic of | wikipedia-en:Meet-in-the-middle_attack |
