Cryptanalysis: Difference between revisions
Jump to navigation
Jump to search
| [unchecked revision] | [unchecked revision] |
imported>Kvng m misnamed |
imported>Sddarealone →See also: Added a link to algebraic attack |
||
| Line 2: | Line 2: | ||
[[File:Cyklometr.jpg|thumb|upright=1.5|Reconstruction of the appearance of [[cyclometer]], a device used to break the encryption of an early version of the [[Enigma machine]]. Based on sketches in [[Marian Rejewski]]'s memoirs.]] | [[File:Cyklometr.jpg|thumb|upright=1.5|Reconstruction of the appearance of [[cyclometer]], a device used to break the encryption of an early version of the [[Enigma machine]]. Based on sketches in [[Marian Rejewski]]'s memoirs.]] | ||
'''Cryptanalysis''' ( | '''Cryptanalysis''' ({{etymology|el|{{translit|el|kryptós}}|hidden||{{translit|el|analýein}}|to analyze}}) refers to the process of analyzing [[information system]]s in order to understand hidden aspects of the systems.<ref name=":0">{{Cite book |last=Dooley |first=John F. |title=History of Cryptography and Cryptanalysis |series=History of Computing |date=2024 |url=https://link.springer.com/book/10.1007/978-3-031-67485-3 |language=en |doi=10.1007/978-3-031-67485-3 |isbn=978-3-031-67484-6 |issn=2190-6831|url-access=subscription }}</ref> Cryptanalysis is used to breach [[Cryptography|cryptographic]] security systems and gain access to the contents of [[Encryption|encrypted]] messages, even if the [[key (cryptography)|cryptographic key]] is unknown. | ||
In addition to mathematical analysis of cryptographic algorithms, cryptanalysis includes the study of [[side-channel attacks]] that do not target weaknesses in the cryptographic algorithms themselves, but instead exploit weaknesses in their implementation. | In addition to mathematical analysis of cryptographic algorithms, cryptanalysis includes the study of [[side-channel attacks]] that do not target weaknesses in the cryptographic algorithms themselves, but instead exploit weaknesses in their implementation. | ||
| Line 17: | Line 17: | ||
===Amount of information available to the attacker=== | ===Amount of information available to the attacker=== | ||
{{main|Attack model}} | {{main|Attack model}} | ||
[[Attack model|Cryptanalytical attacks]] can be classified based on what type of information the attacker has available. As a basic starting point it is normally assumed that, for the purposes of analysis, the general [[algorithm]] is known; this is [[Claude Shannon|Shannon's Maxim]] "the enemy knows the system"<ref>{{cite journal|last1=Shannon|first1=Claude|title=Communication Theory of Secrecy Systems|journal=Bell System Technical Journal|date=4 October 1949|volume=28|issue=4|page=662|doi=10.1002/j.1538-7305.1949.tb00928.x|url=https://archive.org/stream/bstj28-4-656#page/n5/mode/2up|access-date=20 June 2014|ref=Shannon}}</ref> – in its turn, equivalent to [[Kerckhoffs's principle]].<ref>{{citation |first = David |last = Kahn |title = The Codebreakers: the story of secret writing |year = 1996 |edition=second |publisher = Scribners |page=235}}</ref> This is a reasonable assumption in practice – throughout history, there are countless examples of secret algorithms falling into wider knowledge, variously through [[espionage]], [[betrayal]] and [[reverse engineering]]. (And on occasion, ciphers have been broken through pure deduction; for example, the German [[Lorenz cipher]] and the Japanese [[Purple code]], and a variety of classical schemes):<ref>{{cite book|author=Schmeh, Klaus|title=Cryptography and public key infrastructure on the Internet|publisher=John Wiley & Sons|year=2003|isbn=978-0-470-84745-9|page=45|url=https://books.google.com/books?id=9NqidkUqHdgC&pg=PA45}}</ref> | [[Attack model|Cryptanalytical attacks]] can be classified based on what type of information the attacker has available. As a basic starting point it is normally assumed that, for the purposes of analysis, the general [[algorithm]] is known; this is [[Claude Shannon#Shannon's maxim|Shannon's Maxim]] "the enemy knows the system"<ref>{{cite journal|last1=Shannon|first1=Claude|title=Communication Theory of Secrecy Systems|journal=Bell System Technical Journal|date=4 October 1949|volume=28|issue=4|page=662|doi=10.1002/j.1538-7305.1949.tb00928.x|bibcode=1949BSTJ...28..656S |url=https://archive.org/stream/bstj28-4-656#page/n5/mode/2up|access-date=20 June 2014|ref=Shannon}}</ref> – in its turn, equivalent to [[Kerckhoffs's principle]].<ref>{{citation |first = David |last = Kahn |title = The Codebreakers: the story of secret writing |year = 1996 |edition=second |publisher = Scribners |page=235}}</ref> This is a reasonable assumption in practice – throughout history, there are countless examples of secret algorithms falling into wider knowledge, variously through [[espionage]], [[betrayal]] and [[reverse engineering]]. (And on occasion, ciphers have been broken through pure deduction; for example, the German [[Lorenz cipher]] and the Japanese [[Purple code]], and a variety of classical schemes):<ref>{{cite book|author=Schmeh, Klaus|title=Cryptography and public key infrastructure on the Internet|publisher=John Wiley & Sons|year=2003|isbn=978-0-470-84745-9|page=45|url=https://books.google.com/books?id=9NqidkUqHdgC&pg=PA45}}</ref> | ||
* ''[[Ciphertext-only attack|Ciphertext-only]]'': the cryptanalyst has access only to a collection of [[ciphertext]]s or [[codetext]]s. | * ''[[Ciphertext-only attack|Ciphertext-only]]'': the cryptanalyst has access only to a collection of [[ciphertext]]s or [[codetext]]s. | ||
* ''[[Known-plaintext attack|Known-plaintext]]'': the attacker has a set of ciphertexts to which they know the corresponding [[plaintext]]. | * ''[[Known-plaintext attack|Known-plaintext]]'': the attacker has a set of ciphertexts to which they know the corresponding [[plaintext]]. | ||
| Line 26: | Line 26: | ||
===Computational resources required=== | ===Computational resources required=== | ||
{{See also|Time/memory/data tradeoff attack}} | {{See also|Time/memory/data tradeoff attack}} | ||
Attacks can also be characterised by the resources they require. Those resources include:<ref>{{Cite journal|last=Hellman|first=M.|date=July 1980|title=A cryptanalytic time-memory trade-off|journal=IEEE Transactions on Information Theory|language=en-US|volume=26|issue=4|pages=401–406|doi=10.1109/tit.1980.1056220|s2cid=552536 |issn=0018-9448|url=http://www-ee.stanford.edu/~hellman/publications/36.pdf |archive-url=https://ghostarchive.org/archive/20221010/http://www-ee.stanford.edu/~hellman/publications/36.pdf |archive-date=2022-10-10 |url-status=live}}</ref> | Attacks can also be characterised by the resources they require. Those resources include:<ref>{{Cite journal|last=Hellman|first=M.|date=July 1980|title=A cryptanalytic time-memory trade-off|journal=IEEE Transactions on Information Theory|language=en-US|volume=26|issue=4|pages=401–406|doi=10.1109/tit.1980.1056220|bibcode=1980ITIT...26..401H |s2cid=552536 |issn=0018-9448|url=http://www-ee.stanford.edu/~hellman/publications/36.pdf |archive-url=https://ghostarchive.org/archive/20221010/http://www-ee.stanford.edu/~hellman/publications/36.pdf |archive-date=2022-10-10 |url-status=live}}</ref> | ||
* Time – the number of ''computation steps'' (e.g., test encryptions) which must be performed. | * Time – the number of ''computation steps'' (e.g., test encryptions) which must be performed. | ||
* Memory – the amount of ''storage'' required to perform the attack. | * Memory – the amount of ''storage'' required to perform the attack. | ||
| Line 36: | Line 36: | ||
===Partial breaks=== | ===Partial breaks=== | ||
The results of cryptanalysis can also vary in usefulness. Cryptographer [[Lars Knudsen]] (1998) classified various types of attack on [[block cipher]]s according to the amount and quality of secret information that was discovered: | The results of cryptanalysis can also vary in usefulness. Cryptographer [[Lars Ramkilde Knudsen|Lars Knudsen]] (1998) classified various types of attack on [[block cipher]]s according to the amount and quality of secret information that was discovered: | ||
* ''Total break'' – the attacker deduces the secret [[key (cryptography)|key]]. | * ''Total break'' – the attacker deduces the secret [[key (cryptography)|key]]. | ||
* ''Global deduction'' – the attacker discovers a functionally equivalent [[algorithm]] for encryption and decryption, but without learning the key. | * ''Global deduction'' – the attacker discovers a functionally equivalent [[algorithm]] for encryption and decryption, but without learning the key. | ||
| Line 141: | Line 141: | ||
[[Asymmetric cryptography]] (or [[public-key cryptography]]) is cryptography that relies on using two (mathematically related) keys; one private, and one public. Such ciphers invariably rely on "hard" [[mathematical problem]]s as the basis of their security, so an obvious point of attack is to develop methods for solving the problem. The security of two-key cryptography depends on mathematical questions in a way that single-key cryptography generally does not, and conversely links cryptanalysis to wider mathematical research in a new way.<ref>{{Cite web |date=2025-03-21 |title=Cryptology - Cryptanalysis, Encryption, Decryption {{!}} Britannica |url=https://www.britannica.com/topic/cryptology/Cryptanalysis |access-date=2025-04-28 |website=www.britannica.com |language=en}}</ref> | [[Asymmetric cryptography]] (or [[public-key cryptography]]) is cryptography that relies on using two (mathematically related) keys; one private, and one public. Such ciphers invariably rely on "hard" [[mathematical problem]]s as the basis of their security, so an obvious point of attack is to develop methods for solving the problem. The security of two-key cryptography depends on mathematical questions in a way that single-key cryptography generally does not, and conversely links cryptanalysis to wider mathematical research in a new way.<ref>{{Cite web |date=2025-03-21 |title=Cryptology - Cryptanalysis, Encryption, Decryption {{!}} Britannica |url=https://www.britannica.com/topic/cryptology/Cryptanalysis |access-date=2025-04-28 |website=www.britannica.com |language=en}}</ref> | ||
Asymmetric schemes are designed around the (conjectured) difficulty of solving various mathematical problems. If an improved algorithm can be found to solve the problem, then the system is weakened. For example, the security of the [[Diffie–Hellman key exchange]] scheme depends on the difficulty of calculating the [[discrete logarithm]]. In 1983, [[Don Coppersmith]] found a faster way to find discrete logarithms (in certain groups), and thereby requiring cryptographers to use larger groups (or different types of groups). [[RSA (cryptosystem)|RSA]]'s security depends (in part) upon the difficulty of [[integer factorization]] – a breakthrough in factoring would impact the security of RSA.<ref>{{Cite journal |last=Coppersmith |first=Don |date=4 July 1984 |title=Fast Evaluation of Logarithms in Fields of Characteristic Two |url=https://pages.cs.wisc.edu/~cs812-1/coppersmith.pdf |journal=IEEE Transactions on Information Theory |volume=IT-30 |issue=4 |pages=587–594|doi=10.1109/TIT.1984.1056941 }}</ref> | Asymmetric schemes are designed around the (conjectured) difficulty of solving various mathematical problems. If an improved algorithm can be found to solve the problem, then the system is weakened. For example, the security of the [[Diffie–Hellman key exchange]] scheme depends on the difficulty of calculating the [[discrete logarithm]]. In 1983, [[Don Coppersmith]] found a faster way to find discrete logarithms (in certain groups), and thereby requiring cryptographers to use larger groups (or different types of groups). [[RSA (cryptosystem)|RSA]]'s security depends (in part) upon the difficulty of [[integer factorization]] – a breakthrough in factoring would impact the security of RSA.<ref>{{Cite journal |last=Coppersmith |first=Don |date=4 July 1984 |title=Fast Evaluation of Logarithms in Fields of Characteristic Two |url=https://pages.cs.wisc.edu/~cs812-1/coppersmith.pdf |journal=IEEE Transactions on Information Theory |volume=IT-30 |issue=4 |pages=587–594|doi=10.1109/TIT.1984.1056941 |bibcode=1984ITIT...30..587C }}</ref> | ||
In 1980, one could factor a difficult 50-digit number at an expense of 10<sup>12</sup> elementary computer operations. By 1984 the state of the art in factoring algorithms had advanced to a point where a 75-digit number could be factored in 10<sup>12</sup> operations. Advances in computing technology also meant that the operations could be performed much faster. [[Moore's law]] predicts that computer speeds will continue to increase. Factoring techniques may continue to do so as well, but will most likely depend on mathematical insight and creativity, neither of which has ever been successfully predictable. 150-digit numbers of the kind once used in RSA have been factored. The effort was greater than above, but was not unreasonable on fast modern computers. By the start of the 21st century, 150-digit numbers were no longer considered a large enough [[key size]] for RSA. Numbers with several hundred digits were still considered too hard to factor in 2005, though methods will probably continue to improve over time, requiring key size to keep pace or other methods such as [[elliptic curve cryptography]] to be used.{{Citation needed|date=April 2012}} | In 1980, one could factor a difficult 50-digit number at an expense of 10<sup>12</sup> elementary computer operations. By 1984 the state of the art in factoring algorithms had advanced to a point where a 75-digit number could be factored in 10<sup>12</sup> operations. Advances in computing technology also meant that the operations could be performed much faster. [[Moore's law]] predicts that computer speeds will continue to increase. Factoring techniques may continue to do so as well, but will most likely depend on mathematical insight and creativity, neither of which has ever been successfully predictable. 150-digit numbers of the kind once used in RSA have been factored. The effort was greater than above, but was not unreasonable on fast modern computers. By the start of the 21st century, 150-digit numbers were no longer considered a large enough [[key size]] for RSA. Numbers with several hundred digits were still considered too hard to factor in 2005, though methods will probably continue to improve over time, requiring key size to keep pace or other methods such as [[elliptic curve cryptography]] to be used.{{Citation needed|date=April 2012}} | ||
| Line 169: | Line 169: | ||
==See also== | ==See also== | ||
* {{Annotated link|Algebraic attack}} | |||
* {{annotated link|Economics of security}} | * {{annotated link|Economics of security}} | ||
* {{annotated link|Global surveillance}} | * {{annotated link|Global surveillance}} | ||