[Cryptography] Minimal secure boot

sebastien riou matic at nimp.co.uk
Wed Jun 12 18:34:36 EDT 2019

On Wed, Jun 12, 2019 at 7:48 AM Jon Callas <jon at callas.org> wrote:

> The problem with exponent 3 is that there are solutions to a number of
> cubics.
> All exponent 2 systems are easily solvable with our old friend The
> Quadratic Equation. They're not secure.
> There is also a Cubic Equation, which lets you solve cubics. The thing is,
> though, not all cubics can be solved, just some of them.  Thus, what you
> need to do to use exponent 3 is to show that your parameters don't have a
> cubic solution to them. I leave that as an exercise for you to go research.
> Thanks Jon, that's very useful info.

> there are places where PKCS#1 is secure, and places where it is not. Which
> one is your case and why?
That's precisely what I am trying to find out

If you came to us and explained that you were going to use exponent 3,
> PKCS#1, and what all, and outlined a clear set of reasons why, and you
> wanted someone to comment, it's likely we'd ask a few questions and send
> you on your merry way. That's not what you're doing.
That's what I intended to do but apparently I failed :-( I try again below.
Thanks for the long answer, it is very much appreciated.
The scheme:
- a RSA2048 single key pair is generated, with 5 as public exponent.
- The public key is written in the ROM code of a microcontroller product.
- At boot, the microcontroller get software image via UART and use RSA with
PKCS#1 v1.5 and SHA256 to verify its authenticity.
- Secret key is used exclusively to sign software images
- Any given software image is signed exclusively with this secret key
- software images are generated exclusively by us, there is no "malicious"
software image that ever get signed

Some notation used in the rational:
- Generate an RSA2048 key pair
   - d: private exponent
   - n: modulus
   - e: public exponent, fixed to 5
- store n and e in the ROM
- at build time:
   - digest = sha256 over the software image
   - c = PKCS1_15_pad(digest)
   - sig = mod_exp(c,d,n)
   - append sig to code
- at boot:
   - get code and sig
   - digest = sha256 over software image
   - expected = mod_exp(sig,e,n)
   - launch execution of software image only if PKCS1_15_pad(digest) ==

The rational:
- Use 2048 bit key and SHA256 to achieve 128 bit security level.
- public exponent e=5:
   - as indicated by Jon, 3 leads sometimes to weak keys, 5 does not have
this problem
   - "Coppersmith attack" is not a worry since we sign an image only with
one key
   - "Franklin-Reiter Related Message Attack" is not applicable since the
"message" here is sig and its values for different software images are
completely unrelated due to SHA256.
   - Not sure if the "Coppersmith's Short Pad Attack" is applicable,
considering digest as the "short pad" (not clear if the pad value is
recovered by the attack). Even if it does, it would not work because digest
length is 256bits, so longer than len(n)/(e power 2).
   - "partial key exposure attack" is not a problem, the secret key is not
in the device and kept in a HSM in a secure room
   - since we use padding method, we always have "sig power e" greater than
the modulus n.
- static padding scheme:
   - "Bleichenbacher attack" (
does not apply as it is a chosen cipher text attack.
   - "Coron and al attacks" (
http://www.crypto-uni.lu/jscoron/publications/pkcs2000.pdf) do not apply as
they are chosen plain text attacks.

Any pointer to other potential attacks would be appreciated. Incorrectness
in all things above even more so.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20190613/2cd6d481/attachment.html>

More information about the cryptography mailing list