Solving cryptography’s toughest challenge using a key that doesn’t exist
The security lies in secrecy of the key.
Isn’t it obvious that the toughest challenge of any key — lock system is to keep the key secure and make the lock unbreakable? The same is the case of cryptographic systems. According to Kirchoff’s principle, the security lies in the secrecy of the key.
Enemy knows the system i.e. the lock
When designing a cryptographic system, developers tend to assume the details of the system will be known to the enemy at some point. If the algorithm itself is kept in total secrecy, then no one will be able to use it. Which defeats the whole purpose of designing a security system. This idea reformulated in the words of Claude Shannon (father of information theory) as “Enemy knows the system”.
So what we can infer from this?
The key needs to be as secure as possible, and the algorithm should be unbreakable.
The System
If one-way functions exist, then P != NP
A direct definition of One-Way functions is that a function which can give the output in polynomial time, but given an output, it should be impractical to get the input. The idea of a one-way function has already existed in traditional crypto primitives. Like in hashing you can find the hash of input in milliseconds, but given a hash, it takes exponential time to figure out the input. Note that it’s not sufficient to not have an inverse function to be called a one-way function.
The existence of One-way functions is not proven, it’s one of the numerous unsolved problems in complexity theory. If it exists, then P will not be equal to NP. Anyway, let’s not go into those complex theories.
You can say goodbye to bitcoin!!
But now you must be wondering if it’s not sure whether a truly one-way function exists then why is it used for cryptography. Won’t people be able to break it by finding an inverse function? But the key idea is that classical computers which we use now are not capable of finding such an inverse method within a lifetime(exponential time). That’s the security guarantee that classical cryptographic methods have.
PS: Once Quantum computers become a reality, most of the classical cryptographic methods will break. Especially public-key cryptography. And you can say goodbye to Bitcoin
There are attempts to develop quantum-proof protocols that utilize crypto primitives that cannot be broken even by a quantum computer. This type of cryptography is called Post-Quantum cryptography.
So we now understand that the system is unbreakable (for now). The next question is
The key
How to secure the key? — Current methods to store the secret key is by using a nonvolatile memory like EEPROM (Electrically Erasable Programmable Read-Only Memory) or battery-powered SRAM (Static Random-Access Memory). But the issue with this method is that in addition to being power and space-consuming it is always vulnerable to newer kinds of physical attacks. And continually powered extra circuitry is required to protect against such attacks.
What if the key doesn’t exist?
Yes, you heard that right. What if there is a way to derive the key every time it’s required for an encryption or decryption process without the need to store it in memory. Then nobody can steal it. Genius isn’t it ?.
Physical Unclonable Functions
Now, Enter the new dragon i.e. Physically Unclonable Functions or the commonly used abbreviation — PUF is a recent innovation in the field of cryptographic primitives. First proposed as Physical one-way functions in 2001 by Ravikanth S Pappu a Ph.D. student from MIT in his Ph.D. thesis.
The one-way function I mentioned earlier is purely in the mathematical domain. But physical one-way functions derives its output utilizing unique physical properties of a system particularly an Integrated Circuit (IC) as proposed in this paper in 2002 which coined the term ‘PUF’. So basically in simple terms PUFs are one-way functions that utilize the unique physical characteristics of a silicon chip which are naturally formed during the semiconductor manufacturing to produce the output.
The main advantages/features of such a function are:
- PUF can be set up using simple digital circuits that are easy to make and consume less power.
- The input-output mapping of each PUF is unique to it’s IC, thus PUFs are called digital fingerprints of silicon chips
- Since the output is derived during when the IC’s powered on, there is no secret to steal when the chip is idle. The key doesn’t exist in memory until the PUF calculates the output during the process of decryption/encryption.
- Physical attacks are almost impossible to achieve because the physical characteristics of a silicon chip can change during the attack. Then the PUF will no longer give the same outputs. Thus the word unclonable. This is similar to the cryptex (an ancient keystone) that Tom hanks decrypted in the movie Davinci code where the message residing in it will be destroyed if someone used force.{spoiler alert: the key was ‘apple’}.
- PUFs use smaller output bit size (like 64 bits) compared to traditional methods like SHA which requires 256 bits for output. This is why keys derived using PUF input-output pair can make the crypto protocols much faster.
Application
For the Internet of Things, when the embedded devices are placed in open areas. It makes the device more vulnerable to physical attacks. But such devices cannot afford costly key storage methods in terms of energy and size. In such cases, PUFs are better alternatives for identification and authentication of the devices compared to traditional crypto primitives.
Note: from now on we don’t use the term input/output for PUF. We say Challenge-Response(C-R) pair as the research community does.
These challenge-response pairs can be used in certain ways to achieve different cryptographic protocols. The details of which can be explained in another post.
PUFs are not here to completely replace current cryptosystems
But don’t get the wrong idea that PUFs are here to completely replace current cryptosystems like RSA, AES, or SHA. Because PUFs also have disadvantages:
- Once the challenge-response pair stored in the Authentication server is compromised, the attacker will be able to decrypt the messages encrypted using those C-R pairs.
- Since the C-R pairs are discarded after each session, the trusted server has to update it with fresh pairs regularly.
- Various environmental factors can alter the physical characteristics of the chip to produce an error, thus not all challenges will give a stable response.
Through ought the year’s thousands of researchers have come up with various error correction methods and alternatives derivation methods of PUF. But the basic idea remains the same.
Public Physical Unclonable Function
A new variation of PUF has come recently, called Public PUF (PPUF). I will briefly explain the concept behind it. A PPUF has a PUF model along with the hardware PUF formed during the manufacturing process. This PUF model emulates the same challenge-response pair as PUF hardware. But the distinguishing factor is the PUF model takes a much longer but feasible time to calculate the response, compared to PUF hardware. Also with a condition that PUF hardware cannot be made from the PUF model, but model can be derived from the hardware.
the key truly became nonexistent in memory
The advantage of this PUF alternative is that now the server no longer has to store the C-R pair, instead, it keeps the PUF model to derive the response for a random challenge when it requires. This way the key truly became nonexistent in memory on both sides of the communication.
References
- Wiki on PUF-https://en.wikipedia.org/wiki/Physical_unclonable_function#cite_note-ReferenceA-6
- Silicon physical random functions-https://dl.acm.org/doi/10.1145/586110.586132
- Physical Unclonable Functions and Applications: A Tutorial- https://ieeexplore.ieee.org/document/6823677/
- Wiki on one-way functions- https://en.wikipedia.org/wiki/One-way_function
- Physical One-Way Functions-https://science.sciencemag.org/content/297/5589/2026
