[Cryptography] Minimal secure boot

[Jon Callas]

> On Jun 11, 2019, at 12:31 PM, sebastien riou <matic at nimp.co.uk> wrote:
> 
> 
> Knowing I don't know, why wouldn't you use OAEP or some equivalent?
> 
> Thanks for the advices. This is going to a ROM code, this is not general purpose nor updated carelessly by random guys, so I am willing "to take care" if that saves few bytes in my code and/or improves performance. 

Okay. If code size and performance are your major concern over security, why not just have an unsigned ROM? That will save you even more code and be even faster.

I realize I'm being a smartass when I say that, but we're talking security, and you're responding to security questions with answers that are performance and resource answers. If you respond to security questions with performance/resource answers, it means that your important issue is performance and resources. Since security is obviously Job Two if not Three, why not just say, "Gosh, I'd really like to have secure boot, but we can't afford it." That's a much better answer than mediocre security.

> I like e=3 very much, with that I could hardcode the main loop to do 2 identical iterations, saving both code size and execution time.


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.

Going on, exponent 4 is also not secure. I'm sure you can guess why. 

Euler proved that there is no polynomial solution for a polynomial of exponent 5 or higher (there are also exceptions here, like exponent 6, which I also leave as an exercise). 

Normally, cryptographic engineers don't like to use exponent 5 for really bad reasons. Those include that while they use number theory, they seem not to actually believe in it. That's why you typically see 17 or 64k+1. All of those – 3, 5, 17, 64k+1 are of the form of a one bit, a series of zero bits, and then a one bit. Thus, they are faster than an arbitrary exponent. While there's nothing wrong with someone using 3 when they know how and why, you're much better off on the well-worn path.

> On the padding I don't like OAEP because of the increased complexity which will increase code size. 
> For now I settled for PKCS1_1v5 following https://tools.ietf.org/html/rfc8017 <https://tools.ietf.org/html/rfc8017> (with padding hardcoded for SHA256). Of course I will switch immediatly to OAEP if there is a compelling reason to do that, but my understanding is that PKCS1_1v5 is good enough for my purpose.

Okay, there are places where PKCS#1 is secure, and places where it is not. Which one is your case and why?

> 
> So my question can be reformulated as follow: what I would have to ensure to be safe with e=3 and PKCS1_1v5 ?
> - I can take care of not signing the same plaintext with two different keys.
> - I can take care of not signing anything coming from a third party.
> Is there something else to take of ?

You would be much better off using a different exponent – like 5, 17, or 65537 (as stated above), which all have a hamming weight of 2, and OAEP.

Picasso is somewhat notorious for the aphorism, "When I run out of red, I just use blue instead." The thing about this is that if you're Picasso, you can use blue in place of red. If you're otherwise experienced, likely you can, too. You're coming to us and essentially saying, "Hey, I wanna use only blue so I can save money on paint." If you do that, there will be tears. Your painting is not going to look good. You need to learn how to follow the rules before you go break them. Picasso was also somewhat famous for periodically (every couple of years or so) doing an utterly straight, representational painting. He did it for the discipline, but also to how that he wasn't just doing Cubism or whatever because he no longer had it. 

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. You want to cut corners and not your fingers, and you want to start by cutting corners, not start by figuring out how not to cut your fingers. My advice is to come up with a completely secure, bog-standard implementation and *then* look at how you can optimize. Don't start off with optimizing. Start off with security. Be bold, and spend a bit more RAM and ROM on an implementation that you can describe in a couple sentences and a reasonably smart, non-expert person will find good enough. They're the ones who will be your customers and users, after all.

	Jon

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20190611/666133df/attachment.html>