Key finding attacks

Uses your system voice; voice and rate in settings.

Snapshot

≈ 3 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

Key finding attacks are attacks on computer systems that make use of cryptography in which computer memory or non-volatile storage is searched for private cryptographic keys that can be used to decrypt or sign data. The term is generally used in the context of attacks which search memory much more efficiently than simply testing each sequence of bytes to determine if it provides the correct answer. They are often used in combination with cold boot attacks to extract key material from computers.

Key finding attacks are attacks on computer systems that make use of cryptography in which computer memory or non-volatile storage is searched for private cryptographic keys that can be used to decrypt or sign data. The term is generally used in the context of attacks which search memory much more efficiently than simply testing each sequence of bytes to determine if it provides the correct answer. They are often used in combination with cold boot attacks to extract key material from computers. Shamir and van Someren demonstrated one example of this analytical approach for finding private RSA keys where the public key is known and has a small public exponent. In the RSA system the public key is a pair (n,e) , where n=p.q with p and q being two large primes. The corresponding private key is (n,d) (or sometimes (p,q,d) or some variant thereof) where e.d\equiv1\pmod{\phi(n)} , which is to say that e multiplied by d is equivalent to 1, modulo \phi(n) where φ represents Euler's totient function and is the size of the multiplicative group modulo n. In the case of an RSA key: \phi(n)=(p-1)(q-1)=n-p-q+1 Finding the value of \phi(n) from n allows for the factorization of n and the security of the RSA cryptosystem rests on the difficulty of doing so. As such an attacker cannot determine d exactly, given e and n. An attack can however know a fair amount about what d looks like, given the knowledge that p and q are typically chosen to be the same length in bits and are both 'close' to the square root of n. Thus an attacker can approximate a guess of: \phi(n)\approx \phi '(n) = n-2\sqrt{n} and typically this approximation will be correct in the more significant half of its bits of its binary representation. The relationship of e and d means that: d = (1 + k.\phi(n))/e where the exact value of k is unknown but 0 Using this fact and the approximation \phi'(n) , the attacker can enumerate a set of possible values for the top half of the binary representation of d for each possible value of k. These binary patterns can be tested for many orders of magnitude faster than performing a trial decryption. Furthermore, in the common case of e=3 it can be shown that k=2, which allows the top half of the bits of d to be determined exactly and searched for directly.

References

Text derived from https://en.wikipedia.org/w/index.php?oldid=1314516019 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

2 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.