2
$\begingroup$

Here's a quote from Douglas Stinson:

“[i]f a cryptosystem can be ‘broken’ in some specific way, then it would be possible to efficiently solve some well-studied problem that is thought to be difficult. For example, it may be possible to prove a statement of the type “a given cryptosystem is secure if a given integer n cannot be factored.” [...] [B]ut it must be understood that this approach only provides a proof of security relative to some other problem, not an absolute proof of security. This is a similar situation to proving that a problem is NP-complete [...].”

Source: Stinson, D. R. (2006). Cryptography, Theory and Practice. Chapman and Hall, CRC, 3rd edition. Chapter 2, section 2.1, page 45.

Say there is a proof that a cryptosystem $X$ satisfies Stinson's definition. An attacker builds a method to break $X$ by side-channel attacks. Does that offer any trouble to the definition or to my proof? Or would you say side-channel attacks have nothing to do with provable security?

$\endgroup$
2
$\begingroup$

Say there is a proof that a cryptosystem X satisfies Stinson's definition. An attacker builds a method to break X by side-channel attacks. Does that offer any trouble to the definition or to my proof?

Not generally: The proof covers the algorithm, and side channel attacks target the implementation.

If someone threatens to hurt you unless (or until) you give them your private key, that doesn't violate the provable security claim of the algorithm.

The algorithm is an abstract idea, and the provable security guarantee would indicate that no other abstract idea (algorithm) could violate the security without providing a solution to another abstract problem.

Or would you say side-channel attacks have nothing to do with provable security?

More or less, yes; You can't have provable security against rubber hose cryptanalysis, you can't provide security if the attacker is watching over your shoulder as you perform the algorithm with pencil and paper, you can't have security if your program prints it's state at every step of the way to a log file the adversary has access to, etc.

Basically

Proofs rest on assumptions (even if they're not stated explicitly). If you violate those assumptions, then you can skirt around the guarantees provided by the proof.

This is one reason why provably secure algorithms would ideally be combined with side channel resistant techniques (e.g. constant time code, blinding, etc) and formally verified implementations.

$\endgroup$
1
$\begingroup$

A simple analogy; Your bad driving is not related to the manufacturer.


In side-channel attack, you gain information about the underlying operations. For example, due to incorrect implementations, the RSA square-and-multiple modular powering algorithm may leak the key bits by power analysis.

This is nothing to the with the provable security. A careful implementation can overcome of this attack, see BearSSL.

To make it more clear, this is the Wikipedia definition:

In computer security, a side-channel attack is any attack based on information gained from the implementation of a computer system, rather than weaknesses in the implemented algorithm itself.

An interesting side-channel attack on RSA was the acoustic cryptanalysis:

we have shown that different RSA keys induce different sound patterns... we describe a new acoustic cryptanalysis key extraction attack, applicable to GnuPG's current implementation of RSA.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.