[Cryptech Tech] modexp: operands > 1024 (probably) fixed

[Joachim Strömbergson]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256

Aloha!

Rob Austein wrote:
>> At Tue, 30 Jun 2015 16:47:18 +0200, Joachim Strömbergson wrote:
>>> Found the culprits that caused operands > 1024 bits to not work.
>>> I've tested with 2048 bit operands in simulation and it works.
>>> The fixes and new testcases have been checked into master.
>>> 
>>> Would appreciate if you could update and see if your tests goes
>>> through.
> 
> Today's core gets correct answers for 1024, 2048, and 4096 bit RSA.

Good, thanks for verifying. One problem down at least.

> Runtime  for this core (pure ModExp operations only, exponent
> unpadded so we get the fast path benefit for short exponent):
> 
> 1024-bit short exponent (encrypt)           0.450888 seconds 1024-bit
> long exponent (decrypt)            3.553510 seconds
> 
> 2048-bit short exponent (encrypt)           0.000728 seconds 2048-bit
> long exponent (decrypt)            23.387081 seconds
> 
> 4096-bit short exponent (encrypt)           1.365269 seconds 4096-bit
> long exponent (decrypt)            178.863616 seconds
> 
> 
> No, I don't know why 2048-bit encrypt shows up as faster than
> 1024-bit encrypt.  Troubling, as it smells like a potential timing
> attack, but too early to tell whether it's real or a measurement
> artifact (keep in mind that these numbers are just the difference
> between two calls to gettimeofday(), thus at best no more precise
> than that system call).

Yes, that number for 2048 bit short exponent looks very suspicious. That
is 36400 cycles in total and cannot possibly be the correct value.

- -- 
Med vänlig hälsning, Yours

Joachim Strömbergson - Alltid i harmonisk svängning.
========================================================================
 Joachim Strömbergson          Secworks AB          joachim at secworks.se
========================================================================
-----BEGIN PGP SIGNATURE-----
Comment: GPGTools - http://gpgtools.org
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iQIcBAEBCAAGBQJVk53yAAoJEF3cfFQkIuyNyQ0P/idrYAxZgSgSohj4otdBY4b6
KwS6WRpbKw278GT9edKZIHBwE7sMO3q9cD1w1ZQFARMrKKWAfbMyXK9JOTezDwRA
4UpNDjT5UPOGgggwCj2KQNUToIcmNTI8OWMrjdCC1o6L0RAyPvvzmpfUNyba7TiB
tXqgK722HeWJL1qaNOOvoeFnJ3rJwT5ShQfAJPUR3ee/bfqw0RCPbG8mEOMG9Amn
q/2H5GjCcryG8blSmjJVfKvkUaftw5S3E3+M7HTQIhVGkTOvHSHg81qaZEr7kffE
t4VjSo558E1AgweW9qoMW1d0buDx31o/nSTPcxywW3wRZVlO1h/ZYMbWJjoaGhzT
X49jfScV4V0pZQOJqqp3KfToRBd8EAI36ixh64xK4W05WXA7v25xP7HMEzF56OP3
StNn1L5nx6bg83qTGvnEcL5g5rdj7NSKGL2fZAFa46JxODZ3dECshDWaayFmTthf
TT4hVaidlUnPPDL9hM+7TmOlgB7x5oz4B9OlAIh9/3BI05Dh5E2iRsNO/gy+3PR1
4TGF1Q0wquSBdSOs1ftMsyEpFUvEB6PRq3cgAk0oVYXI0xt0yzvUlPRBYaa63TWc
AS5m0c6ZBO2jsPltqKCd1TcK54CTEjvEVurBQJj61zGlE+NM8NzfnsMx6abkvh+n
v/XnQhxnckJVmzFX+dDi
=uOEl
-----END PGP SIGNATURE-----