RE: Exponent 3 damage spreads...
Anton Stiglic
Fri, 22 Sep 2006 06:39:56 -0700

O.k., thanks to Hal Finney for pointing out to me in a private email that my
modulus wasn't in fact the right size.  I have had some problems with the
openssl key generation (doesn't always seem to generate the exact modulus
size I ask for).  

In attachment, the forged signature opensslB-fake-bin.sig on
messageBunicode.txt which can be validated using the new key I generated
bellow.  I took the same s that I computed beforehand, without reducing it
this time.  The value s is independent of the value of the modulus of the
public key (only dependency is the size)

So here are the instructions, once again (but I bit simplified):

I followed the instructions of Hal Finney's excellent post:
http://www.mail-archive.com/cryptography@metzdowd.com/msg06537.html

I started out by generating 3072 RSA key pair, with public exponent e = 3.

openssl genrsa -des3 -3 -out my.key 3072
(make sure that the modulus is really 3072 bits, no less no more).

the resulting key can be found at the end of this post, the passwords is
"test" if you ever want to use it. I also included the public key
certificate by itself.  All in PEM format.

I created a plaintext message messageBunicode.txt on which I want to forge a
signature.  The file can be found in attachment, it is in Unicode because I
wanted to also try this out with a VBscript implementing a signature
function using CAPICOM, in which all plaintext is transformed into UNICODE
(pretty annoying!). 

The hash of this file is

openssl dgst -sha1 messageBunicode.txt
SHA1(messageBunicode.txt)= 5d89b46034e0f41a920b2fa964e230ebb2d040b0

Now, let's create a valid signature over messageBunicode.txt using the
private key, just to see what the output looks like:

openssl dgst -hex -sha1 -sign my.key messageBunicode.txt
Enter pass phrase for my.key:
SHA1(..\messageBunicode.txt)=
bb029c611d34e98188eb23bd1a836ec7305e94fc726577a59c8dab927fb6c5b3fce549be389f
6b15d8608c15a256f4209c7e76ed1186d8382242d53ee36e47b2d8ccb09be0440dcdcb373e37
967cfbe9d38b12a16dc9aa78e20e1303f8033f27b4c679dc215ac56b4bf33edc2c50f73d3da9
424bc072de81674b1905020546a9e57e3f96ceef7932751b94883f0409577ed7c0aa8cbed272
8dabf2a6df334357df2cabf7f5282107b6ec99e2bf0f65cd992a97f2f3e004e35739a368823c
4c0cebe4fdff53a9f039c2d85e57feff81284c7db97823359d9982da23707c8a48923e16e09e
13803cb5da3d87b94d32b5241198d91d490a3d1b343448b528e853d2add80679054e39e2e21c
1096ba66100ea73559c283c4f281fbf82fa292e6bc1dc5df5773affc3ea2425ce95ac779e7d7
90f59d11e3527d5645d9580bbf68909c2a1c4672204859cf46caa247186d917241a79224c9b6
95499644aeea43daefdc5438e9b96952771f1fbc809655ef5a5a5a148ffd47197369f4a85498
3220596a

Now, let's do some bignumber math.
I wanted to look at the value obtained when you verify a signature (RSA
encrypt the signature with exponent 3).  I use BC, a bignumber calculator I
like allot:
http://www.gnu.org/software/bc/
A version that can be installed on Windows:
http://gnuwin32.sourceforge.net/packages/bc.htm

I use a fast modexp function I implemented for BC, available at
http://crypto.cs.mcgill.ca/~stiglic/Programming/modgroup.bc

You can load it by simply calling bc like this:

bc modgroup.bc

I did all the calculations in hex, so typed the following in bc

obase=16
ibase=16

Now, denote by sp the signature given above, e = 3 and m is the modulus in
the public key certificate I generated.  When pasting the values into BC,
the hex digits need to be in capital letters.  You can get the value of the
modulus by using an ASN.1 interpreter, such as ASN.1 Editor or Peter
Gutmann's dumpASN1 program.  Here are the BC calculations:

sp
BB029C611D34E98188EB23BD1A836EC7305E94FC726577A59C8DAB927FB6C5B3FCE5\
49BE389F6B15D8608C15A256F4209C7E76ED1186D8382242D53EE36E47B2D8CCB09B\
E0440DCDCB373E37967CFBE9D38B12A16DC9AA78E20E1303F8033F27B4C679DC215A\
C56B4BF33EDC2C50F73D3DA9424BC072DE81674B1905020546A9E57E3F96CEEF7932\
751B94883F0409577ED7C0AA8CBED2728DABF2A6DF334357DF2CABF7F5282107B6EC\
99E2BF0F65CD992A97F2F3E004E35739A368823C4C0CEBE4FDFF53A9F039C2D85E57\
FEFF81284C7DB97823359D9982DA23707C8A48923E16E09E13803CB5DA3D87B94D32\
B5241198D91D490A3D1B343448B528E853D2ADD80679054E39E2E21C1096BA66100E\
A73559C283C4F281FBF82FA292E6BC1DC5DF5773AFFC3EA2425CE95AC779E7D790F5\
9D11E3527D5645D9580BBF68909C2A1C4672204859CF46CAA247186D917241A79224\
C9B695499644AEEA43DAEFDC5438E9B96952771F1FBC809655EF5A5A5A148FFD4719\
7369F4A854983220596A
m
C68C6FEA9A08822C1DA79D4D975F95BF9EB56A906A66F7B63AF7CFC5B7A43012DDB4\
2779002AFE4109922FA7B98CECDED22CADDBF1B1F116C79E9068D62A3B371318EA1C\
56CA2106F196D0E6E8DE2D95D300935F5942638220073E311EB59FE9E2D7F000084E\
F753A415E47E42604175F4B7F1AF52838B0BBA5769120B8DAFA1FFB5C96D961BA1E5\
20717202DE09379F34960F03FE196F0A97704BFE32A5DF0D81445E8DDBAF750B5213\
3EBF07D4859032AE392F161544BE5860579ABA6A6F34395D44754DC24C5C37D90F7F\
017F7225F4EA20D4EADD7BEAFA9025D6D58B49DB151FB6C5C5F2CF6BE9175DCFE96D\
5B752C00D71F032C6E89DEE85514816C50AC70D53A6417B30E93EA640E0E274BE926\
4E94C9D1BE835EE252EB9550AFB7E26DCD3E42407F0797332562C2CA202A5A7C200A\
F499C21CFB1367AE831F3A2F55BAA28645A4A25E113298DE767FF784E3C23C9DA3DC\
DC35E397B2779DBA83637AC620C591F656DAD1190CC161652F2FF1BC44F26A1FA8B1\
41EF1A92D1568C1165B9

I verify that my modulus is of the right size:
bits(m)
C00

C00 hex is 3072, good.

Now do RSA verification:

modexp(sp, 3, m)
1FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF\
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF\
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF\
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF\
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF\
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF\
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF\
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF\
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF\
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF\
FFFFFFFFFFFFF003021300906052B0E03021A050004145D89B46034E0F41A920B2FA\
964E230EBB2D040B0

You can see the 01 FF FF FF .. FF pattern followed by 
003021300906052B0E03021A05000414
which is the ASN.1 header (with 00 in front of it) followed by 
5D89B46034E0F41A920B2FA964E230EBB2D040B0
which is the hash of messageBunicode.txt as we calculated above.

Now, let's do the calculations fro  Hal's post, using the above ASN.1 header
(which is the same for all signatures using the above key and the SHA1
algorithm, and you don't need a valid signature to get the value, it is
predictable), with the hash of messageBunicode.txt in order to forge a
signature over the content of messageBunicode.txt 

Since we are calculating in hex, here are the equivalences of the exponents
which are given in decimal in Hal's post:
288d = 120h
1019d = 3FBh
34d = 22h

Now, in bc, using the notations of Hal's post :

d=003021300906052B0E03021A050004145D89B46034E0F41A920B2FA964E230EBB2D040B0
n = 2^120 - d
n
FFCFDECFF6F9FAD4F1FCFDE5FAFFFBEBA2764B9FCB1F0BE56DF4D0569B1DCF144D2F\
BF50

(you can verify that n is divisible by 3)

s = 2^3FB - (n*2^22)/3
s
7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF\
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF\
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEAAEAD6EAB6B2B18EBD595822B1555\
AC5D20CF08046814578C2B994E1DBD8413A43C0564000000000

Now let's look at s^3
1FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF\
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF\
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF003021300906052B0E03021A05000\
4145D89B46034E0F41A920B2FA964E230EBB2D040B00000000000000000000000000\
00000000000000000000000000000000000000000000000000000000000000000000\
0000000002A9AA11CBB60CB35CB569DDD576C272967D774B02AE385C6EE43238C8C9\
1477DBD0ED06ECF8BC4B8D3DC4D566FA65939092D09D13E0ED8F8BE5D5CB9E72C47C\
743B52BBFA7B9697FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFDA285694CD9347AB7528\
D15F9D0DBF0C82C967D1C7CA3CCF69D2E09519FEAD7B96F1FCCB6D7D78AC9B244C2D\
85C08FEE0982D080AB2250A546F64BF15B1C540EA5655A36E52756CC57BBB11BBA3B\
81D72CE1FB7EBFB784027F3087CA7078541278C45764E6F2B1F3E532400000000000\
00000000000000000

This has the form we are looking for, the 01 FF FF ... FF header that ends
with 00, and then we have 
03021300906052B0E03021A050004145D89B46034E0F41A920B2FA964E230EBB2D040B0
which is the d we started out with, and the rest is the GARBAGE part.

Let's look at the modexp calculation

modexp(s, 3, m)
1FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF\
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF\
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF003021300906052B0E03021A05000\
4145D89B46034E0F41A920B2FA964E230EBB2D040B00000000000000000000000000\
00000000000000000000000000000000000000000000000000000000000000000000\
0000000002A9AA11CBB60CB35CB569DDD576C272967D774B02AE385C6EE43238C8C9\
1477DBD0ED06ECF8BC4B8D3DC4D566FA65939092D09D13E0ED8F8BE5D5CB9E72C47C\
743B52BBFA7B9697FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFDA285694CD9347AB7528\
D15F9D0DBF0C82C967D1C7CA3CCF69D2E09519FEAD7B96F1FCCB6D7D78AC9B244C2D\
85C08FEE0982D080AB2250A546F64BF15B1C540EA5655A36E52756CC57BBB11BBA3B\
81D72CE1FB7EBFB784027F3087CA7078541278C45764E6F2B1F3E532400000000000\
00000000000000000

Great!


I saved this value in a file in order to try to verify it with OpenSSL.  
I converted the value to binary. The result can be found in attachment.  I
added leading 00s to make it the size of a normal signature (I think you
have to do this to get the signature to be validated by Openssl).  

An unpatched version of Openssl validates it:

C:\crypto\openssl-0.8.3c>openssl dgst -prverify ..\my.key -sha1 -signature
..\op
ensslB-fake-bin.sig ..\messageBunicode.txt
Enter pass phrase for ..\my.key:
Verified OK

Great, it works!

(I used the private key to validate it here, but you can of course use just
the public key).

--Anton



-----BEGIN RSA PRIVATE KEY-----
Proc-Type: 4,ENCRYPTED
DEK-Info: DES-EDE3-CBC,80575E895271B8B9

W6vYZotX2T1GVqL1WZaF9DfOSjyIC/rnMUgfdKAMgRm7RzIJ4p1WowqG1J9unQIh
l4t2bfDzemtTX5Ke/zP0ClHIB9L+P51JFEI3NlAam42bNKAX60vqX6GZkoiQDxJR
9E60xgfLlO/Tr5AcaNPFnGwfQ9n3T2yOm6mwbPgKQj9+S+hoj4xlYO9auZ7AqaxQ
YsDJDNU/KZYAZQyWisEnbAL154BVeCWWyPf8v8xBjwyxutBsnbQIueObBW6IDQpy
8hrC64TL3wSGbXXHFUs23T3y5adPiiSPZpYEhYoM4Wb+9/NERoSAzqTNPXi8MYbE
NuaaMet15txaCIisyHp1La0uK3mbw1+yJ9xFZD4dcqoBfEkKfK2hgav3uSt4Izhe
M7VqpX21+HqZLRcbABTcXAL9SpuMsSBA+dJxxQgyOGgbxP806UgDem73OoWXp/SO
2ld7ybCvPkz38HQIo1yCM3s+GSfdxLpiKZT/GGB5rqJJNYOZ1BwFM0PGQEBGl1qO
XbENTNm3/SO1eHUkq0wZ8v1mgqW29wH7LpryPHiw7o5/j2tk2iAcgndEdpN5Z+/x
mV6zSsq/uPxouOZtCAPpbRfQ5AY3Qh9d0hX8sNQz/rw2gnytzChBjO90giUAl1Qn
pafi1skidkqyeouq7GyCZGCbBok49cF268uVGlm3qMUqIU05DDeyJjqTrVelzDA/
aJR+9E4ly6YhKt4S+Lm3TFrh5BGZ1me2U9DNMH1Rzde8u+vk6qrN2SQ2RzGVGCEN
Mng/9ApUDni2p5GZLQ4l4d3+GZy38RkCk5J5OfKwsOE6wVdpxGiaugGlTaVyhujE
WjdIAizlh8KWKgGETMdfKU3rbPfLCKLQQivygVlxutLsamBesdTzMZJ47zPIgoO/
GobqrNCYHPTAZc6YxlCOgmMjG6ny4kbR+eSHaHWXiux97M/XTkTe5AhDAbPK0mBP
tAE2YI1aZ1rC/yGaM0eaFQfSTD4bBUuVBjfIuhwSPP6AzSF4+g4/IfRaQfc/OXTe
lffbgRD+vMr3TsI42glGmmhpH1cjpfgyoux0Zj7vN4VUMBJe2kD5J7B/4d6hWPjZ
+osA+tLA8J+Sxx6DSVYULVfbaJ29N2v/ewla2nbxiDX1nQHlyF71dqp2xxR1NdZe
cJqN9VJ+H64qbNZr6WvIvEZyIqBEirf5h7P111/YYUMbcuCAA/QJsjKfU13N/xO1
e9n7I9aXncXn+LCG9/VVUzTZ09ZEnOAzsDZHkInjr2yanGzjcpi0P39Hfr4SgDoS
WAaR/offK/Voq76ClXt8yzXgyw2Ygf3zoARpMrS8mRu7s6KpTXzXefbdv/KX7nFp
kum5DdfFZdFjFOEeuS41ib9rxFzeCVIE8KT4IJ5va5g2Fs22xNH8HZa+wUUBmP+B
FPACav6jh9lGCs00YcCl9wkbeEVEs0awPUjoo4WOqnh4AXb4oWxLiTm6kDxvbTd0
E5/UABTCuOwJAQvXA+tgxEED30/soN/23KdEjREZDkLd8x1g65epTaD7qE1WN8/O
rmy9kYSMwTTUUqPu4xOXiQf7D0qalQ2sykfKmhgj5a4BnhFnUWkjzZ0iCnEQVeLk
7iU+HWm4BQdVR37oq+tnRiURD/d/Rfn5ElSfQo7XMwFSkJw5XEtW/D0piHX2AS2b
WN1rRg3We0MijDXLm5Q7KcneYkt1EtDi45xmEguM6bOZcpOoLglDvmrzK+kOUp88
A6YmQzDjS9M5aO+r1AdfGFtGr5lanjxa6/xy2Jx2tWeEqHx7N7mViMn/ObeQa1Ew
YPAnl9CUMqqcTMU3XpG1qoukEzbWL4gh13BK79PoI3mv+sEsOZY5LuNpvsRkT3A1
gdktvlTkYmsiK6hTnfAZxeifLNoSjukiPt4SJKrIJwto/1cj1tTZ83nItrylXVUD
7EwRtE9fTnzyVayTPmTB4pJiYCDV3uvwuAT/uxnngDtiMUYGXKjgyfZGxNSeA1n5
d5o0pF+2D4gKqqkiP4XbehNjUnusODecXHuJw9+yy5YKtCLesypJqgEmeiYCI2QW
p51Ito+mzH0eu+QPhcVXh6/HbBFKimvzt48S6ZFnDReU3gvOqGlR02wDl4WCRMTq
Coe72TPwnzIA8gh+G5lj9YLNeVnY/E7ywyJpQWntFgsySNwt0Ew2W82+53iAOm+6
U2k4+m/lE18TSJPDp1C5edMtQmTHIHn/FbKLpiCyyzcEV1hUDby5I6E/DuSjbOdO
NnQks8b55Sush9rfSLMLOvqCBWvifTb6Bg23C5/J95inTr6HpMY7Ih75VR+bbYC1
wno0Df/n7M3bNjgWL4Cf4HmWdwmvd06EPkYVCbS3DO7bPeokxtKsZr9mWMH0T4QC
-----END RSA PRIVATE KEY-----

-----BEGIN CERTIFICATE-----
MIIFFjCCA36gAwIBAgIJAKK8Rqxs5gNYMA0GCSqGSIb3DQEBBQUAMGUxCzAJBgNV
BAYTAkNBMQswCQYDVQQIEwJRQzERMA8GA1UEBxMITW9udHJlYWwxFjAUBgNVBAoT
DUluc3RhbnQgTG9naWMxDDAKBgNVBAsUA1ImRDEQMA4GA1UEAxMHTXIgRm9vMjAe
Fw0wNjA5MjIwMzEzMzBaFw0wOTA2MTkwMzEzMzBaMGUxCzAJBgNVBAYTAkNBMQsw
CQYDVQQIEwJRQzERMA8GA1UEBxMITW9udHJlYWwxFjAUBgNVBAoTDUluc3RhbnQg
TG9naWMxDDAKBgNVBAsUA1ImRDEQMA4GA1UEAxMHTXIgRm9vMjCCAaAwDQYJKoZI
hvcNAQEBBQADggGNADCCAYgCggGBAMaMb+qaCIIsHaedTZdflb+etWqQamb3tjr3
z8W3pDAS3bQneQAq/kEJki+nuYzs3tIsrdvxsfEWx56QaNYqOzcTGOocVsohBvGW
0Obo3i2V0wCTX1lCY4IgBz4xHrWf6eLX8AAITvdTpBXkfkJgQXX0t/GvUoOLC7pX
aRILja+h/7XJbZYboeUgcXIC3gk3nzSWDwP+GW8Kl3BL/jKl3w2BRF6N2691C1IT
Pr8H1IWQMq45LxYVRL5YYFeaumpvNDldRHVNwkxcN9kPfwF/ciX06iDU6t176vqQ
JdbVi0nbFR+2xcXyz2vpF13P6W1bdSwA1x8DLG6J3uhVFIFsUKxw1TpkF7MOk+pk
Dg4nS+kmTpTJ0b6DXuJS65VQr7fibc0+QkB/B5czJWLCyiAqWnwgCvSZwhz7E2eu
gx86L1W6ooZFpKJeETKY3nZ/94Tjwjydo9zcNeOXsneduoNjesYgxZH2VtrRGQzB
YWUvL/G8RPJqH6ixQe8aktFWjBFluQIBA6OByjCBxzAdBgNVHQ4EFgQUOL/DKxxT
Bcxysnuc0Fkh5/UZ6YowgZcGA1UdIwSBjzCBjIAUOL/DKxxTBcxysnuc0Fkh5/UZ
6YqhaaRnMGUxCzAJBgNVBAYTAkNBMQswCQYDVQQIEwJRQzERMA8GA1UEBxMITW9u
dHJlYWwxFjAUBgNVBAoTDUluc3RhbnQgTG9naWMxDDAKBgNVBAsUA1ImRDEQMA4G
A1UEAxMHTXIgRm9vMoIJAKK8Rqxs5gNYMAwGA1UdEwQFMAMBAf8wDQYJKoZIhvcN
AQEFBQADggGBAEHPhZODhgPRp2mGcXQaB21E3w39kf82hPRe2VJk229G9g3p6glR
YoEE4rc/pCMW8KLawcxGUlLzmpObVs/rIZ/5TN1mVW3h1VRX+OtYpVRYsAmNnRrV
wpGCtY8qh0zFFTBXpL7OTpraoVv4yla6FUB08lcbjnkiqMof/JEKox+xMYXNylWd
GVqyftMvq8X5vYKcgpY1AiPbnzWWjpOAw9KtEU//EcqtT71aiC5zrSqpIGTIlwyp
wP9HnoASIdOChmVl8C/Dg5+RDilcqkSyH5BA7MOUHpAvKO3XSye3GJ9jnV7fOKnJ
ix/DW8rjG+p07+eC8xP06ZUlvaIyl0VDnW6VBhJr6/+ZgFcqq4ZNuqI7u5TwJDWb
wVyCie1YO3xZMvJ/iQE3yHKkPjTt/9DfocdeUhSX27OCXIzzDazWOW50DCdpg4a4
eOtt5qxPzbPZNZYO3/nT/o4vg0Jq1Nz1lRojqN28/17jdkXBIetGkwFQW4xHpElO
dma8/OvGnTgCIQ==
-----END CERTIFICATE-----