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.
In their seminal paper[1] on Key Finding attacks, Shamir and van Someren proposed two different approaches to key finding: statistical or entropic key finding and analytical key finding. The former relies on detecting differences in the statistical properties of the data that make up cryptographic keys while the later relies on determining specific byte patterns that must necessarily exist in the target key material and looking for these patterns.
In general for most cryptographic systems the cryptographic keys should be as random as possible. For most symmetric ciphers the keys can and should be a truly random set of bits. For most asymmetric ciphers the private keys are either numbers chosen at random with certain constraints (such as primality or being generators in a group) or are the result of computations based on a set of random numbers with some constraints. In either case the key material exhibits high entropy. In contrast to this, most uncompressed data in a computer's memory has relatively low entropy. As a result, if a key is known to exist in memory in its raw form then it is likely to stand out against the background of non-key data by virtue of its high entropy and an attacker needs to only test for matching keys in areas of memory or storage that have high entropy.The contrast between the low entropy of most data and the high entropy of key data is sufficient as to be apparent by visual inspection. The image to the right shows an example of this.
While statistical key finding can be effective for reducing the amount of memory that needs to be searched, it still requires high-entropy areas to be tested to check if they contain the correct key material. In certain cases, particularly in the context of public key encryption systems, it is possible to determine patterns that must occur in the key material and then limit the search to areas where these patterns are found.
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)
n=p.q
(n,d)
(p,q,d)
e.d\equiv1\pmod{\phi(n)}
\phi(n)
\phi(n)=(p-1)(q-1)=n-p-q+1
Finding the value of
\phi(n)
\phi(n) ≈ \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<k<e.
\phi'(n)
e=3
k=2,
Key finding attacks have been used in conjunction with cold boot attacks to extract keys from machines after they have been switched off.[2] Heninger and Shacham showed that keys can be extracted even when the data in memory has been corrupted by having the power removed.[3]
Statistical key finding was used by Nicko van Someren to locate the signature verification keys used by Microsoft to validate the signatures on MS-CAPI plug-ins. One of these key was later discovered to be referred to as the NSAKEY by Microsoft, sparking some controversy.[4]
Key finding attacks can be mitigated in several ways. For analytic attacks, randomized key blinding will prevent the expected patterns from being found in memory as well as protecting against some other sorts of side-channel attack. Statistical attacks can be made less effective by storing other sorts of high-entropy or compressed data in memory and key material can be spread over a larger block of memory when not in use to reduce the concentration of entropy in one place.