<div dir="ltr"><div dir="ltr"><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Wed, Jun 12, 2019 at 7:48 AM Jon Callas <<a href="mailto:jon@callas.org">jon@callas.org</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div style="overflow-wrap: break-word;"><br><div><div>The problem with exponent 3 is that there are solutions to a number of cubics.</div><div><br></div><div>All exponent 2 systems are easily solvable with our old friend The Quadratic Equation. They're not secure.</div><div><br></div><div>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.</div><div><br></div></div></div></blockquote><div>Thanks Jon, that's very useful info.<br></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div style="overflow-wrap: break-word;"><div><div></div><div>there are places where PKCS#1 is secure, and places where it is not. Which one is your case and why?</div></div></div></blockquote><div>That's precisely what I am trying to find out<br></div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div style="overflow-wrap: break-word;"><div></div><div>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. </div></div></blockquote><div>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.<br></div><div>The scheme:</div><div>- a RSA2048 single key pair is generated, with 5 as public exponent.</div><div>- The public key is written in the ROM code of a microcontroller product.<br></div><div>- At boot, the microcontroller get software image via UART and use RSA with PKCS#1 v1.5 and SHA256 to verify its authenticity.<br></div><div>- Secret key is used exclusively to sign software images</div><div>- Any given software image is signed exclusively with this secret key</div><div>- software images are generated exclusively by us, there is no "malicious" software image that ever get signed<br></div><div><br></div><div>Some notation used in the rational:</div><div><div>- Generate an RSA2048 key pair</div><div>   - d: private exponent</div><div>   - n: modulus</div><div>   - e: public exponent, fixed to 5<br></div>- store n and e in the ROM<div>- at build time:</div><div>   - digest = sha256 over the software image</div><div>   - c = PKCS1_15_pad(digest)<br></div><div><div>   - sig = mod_exp(c,d,n)</div><div>   - append sig to code<br></div></div><div>- at boot:</div><div>   - get code and sig</div><div>   - digest = sha256 over software image<br></div><div>   - expected = mod_exp(sig,e,n)</div><div>   - launch execution of software image only if PKCS1_15_pad(digest) == expected</div></div><div><br></div><div>The rational:</div><div>- Use 2048 bit key and SHA256 to achieve 128 bit security level.<br></div><div>- public exponent e=5: <br></div><div>   - as indicated by Jon, 3 leads sometimes to weak keys, 5 does not have this problem<br>   - "Coppersmith attack" is not a worry since we sign an image only with one key</div><div>   - "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.<br></div><div>   - 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).<br></div><div>   - "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 <br>   - since we use padding method, we always have "sig power e" greater than the modulus n.</div><div>- static padding scheme:<br></div><div>   - "Bleichenbacher attack" (<a href="http://archiv.infsec.ethz.ch/education/fs08/secsem/bleichenbacher98.pdf">http://archiv.infsec.ethz.ch/education/fs08/secsem/bleichenbacher98.pdf</a>) does not apply as it is a chosen cipher text attack.<br></div><div>   - "Coron and al attacks" (<a href="http://www.crypto-uni.lu/jscoron/publications/pkcs2000.pdf">http://www.crypto-uni.lu/jscoron/publications/pkcs2000.pdf</a>) do not apply as they are chosen plain text attacks. </div><div> </div><div>Any pointer to other potential attacks would be appreciated. Incorrectness in all things above even more so.<br></div><div>Sebastien<br></div><div><br></div></div></div>