RE: Exponent 3 damage spreads...

2006-09-20 Thread Anton Stiglic

I tried coming up with my own forged signature that could be validated with
OpenSSL (which I intended to use to test other libraries).  I haven't
succeeded, either because in the particular example I came up with OpenSSL
does something that catches the invalid signature, or I messed up somewhere
(the likelihood of which is far from negligible).  Unfortunately, I don't
have much more time to play with this.  I decided to share the methodology I
used with those of you who are interested in case the info is helpful to
anyone, or someone can tell me why the signature I produced doesn't get
validated by OpenSSL.

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

the resulting key can be found bellow, the passwords is test if you ever
want to use it.

Then I created the corresponding public key certificate:

openssl req -new -x509 -days 1001 -key my.key -out my.cer

The public key certificate can be found bellow as well.  You can import this
in Windows key store, for example.

I then created a plaintext file, messageAunicode.txt, for which I computed a
signature on (a valid signature).  The idea was then to forge a signature on
an alternate messageBunicode.txt, without using the private key of course.
The two files can be found in attachment, they are in Unicode because I
wanted to also try this out with a VBscript implementing a signature
function using CAPICOM. (you can get a file in Unicode by opening it with a
simple text editor that allows you to save as Unicode, such as notepad, and
erase any extra bytes (header) with a hex editor such as XVI32).

The hashes of these files are

openssl dgst -sha1 messageAunicode.txt
SHA1(messageAunicode.txt)= eb8302606217ae549fe6ab1345f0b4c804195367

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

Now, create the valid signature over messageAunicode.txt to see what the
output looks like:

openssl dgst -hex -sha1 -sign my.key messageAunicode.txt
Enter pass phrase for my.key:
SHA1(messageAunicode.txt)=00d3cda91b578b6df29aeb140272bd9198759f79fa10dc410b
5d10362048ac7abe5df7fe0d94a6646e791c5b95b29f2c6384a570769dc888ed0b7ad510ccd3
c758cebeb648511620490e0fd54162badb1ed05411acc853509b62a4c1b242e1e2f737a1e7e4
340f5a79b05ec3475d7ba6fc73b3302f1258abac1079f11e8dfb9fc09d42716ba4054add460b
b12fc1b0b8d5d32db50395374aeb3c215c2bc566328d2f03bf043068c5c9abc649ba1767e97d
f32b6aa734594ee22fffe7fb06ea3b77030e79bd6fe7683ab7ffce462abfba5777b3914de466
5b86c1ec203feb6fccb3dadb8ba51fd87a7457c62385418e65d17809c4256e3d27dc2017d7a0
93c8bd193a09168f34d522dd7d3afb95fc61c9f4339091cf25d78bf461b4ea5620eed722ab7d
3eff99cea4a4f546bff6ce338d7763aff20a9b61452da07179590d3316bbce63b06b43d996d7
75d6843f46633ff107a3c866e3b0a8aaaea31f4a2048c9fcb448958287f8e961c9f3393e18fc
9a05460d51a286737aec14a1a7b27a51

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 the calculations all in hex, so typed the following in bc

obase=16
ibase=16

Now, denote by s 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 a ASN.1 viewer, such as ASN.1 Editor or Peter Gutmann's
ASN1dump.  Here are the BC calculations:

s=00D3CDA91B578B6DF29AEB140272BD9198759F79FA10DC410B5D10362048AC7ABE5DF7FE0D
94A6646E791C5B95B29F2C6384A570769DC888ED0B7AD510CCD3C758CEBEB648511620490E0F
D54162BADB1ED05411ACC853509B62A4C1B242E1E2F737A1E7E4340F5A79B05EC3475D7BA6FC
7B3302F1258ABAC1079F11E8DFB9FC09D42716BA4054ADD460BB12FC1B0B8D5D32DB50395374
AEB3C215C2BC566328D2F03BF043068C5C9ABC649BA1767E97DF32B6AA734594EE22FFFE7FB0
6EA3B77030E79BD6FE7683AB7FFCE462ABFBA5777B3914DE4665B86C1EC203FEB6FCCB3DADB8
BA51FD87A7457C62385418E65D17809C4256E3D27DC2017D7A093C8BD193A09168F34D522DD7
D3AFB95FC61C9F4339091CF25D78BF461B4EA5620EED722AB7D3EFF99CEA4A4F546BFF6CE338
D7763AFF20A9B61452DA07179590D3316BBCE63B06B43D996D775D6843F46633FF107A3C866E
3B0A8AAAEA31F4A2048C9FCB448958287F8E961C9F3393E18FC9A05460D51A286737AEC14A1A
7B27A51
m=01D851D5148345606F586935D227CD5CF7F04F890AC5024178BA5F4EE85D7796918C3DC7A5
951C985539CB240E28BA4AC3AFBE0F6EB3151A0DBAFD686C234A30D07D590D61A5474491BF0D
68E1AC7F94CDC989C19C2E25B12511A29FFAF5F11E0B994E19C5C3DC298F9E584FFF3C7DBB8F

RE: [cryptography] Re: Why the exponent 3 error happened:

2006-09-20 Thread Kuehn, Ulrich
 
 From: Ralf-Philipp Weinmann 
 [mailto:[EMAIL PROTECTED] 
[...]
 Unfortunately we only found out that there has been prior art 
 by Yutaka Oiwa et al. *AFTER* we successfully forged a 
 certificate using this method (we being Andrei Pyshkin, Erik 
 Tews and myself).
 
 The certificate we forged however adheres to the padding 
 specifications unlike the one by Yutaka Oiwa that Simon 
 Josefsson forwarded to the list a couple of days ago:
 
 -BEGIN CERTIFICATE-
 MIICgzCCAWugAwIBAgIBFzANBgkqhkiG9w0BAQUFADBoMQswCQYDVQQGEwJVUzEl
 MCMGA1UEChMcU3RhcmZpZWxkIFRlY2hub2xvZ2llcywgSW5jLjEyMDAGA1UECxMp
 U3RhcmZpZWxkIENsYXNzIDIgQ2VydGlmaWNhdGlvbiBBdXRob3JpdHkwHhcNMDYw
 ODE5MTY1MTMwWhcNMDYxMDE4MTY1MTMwWjARMQ8wDQYDVQQDEwZIYWNrZXIwgZ8w
 DQYJKoZIhvcNAQEBBQADgY0AMIGJAoGBAKSu6ChWttBsOpaBrYf4PzyCGNe6DuE7
 rmq4CMskdz8uiAJ3wVd8jGsjdeY4YzoXSVp+9mEF6XqNgyDf8Ub3kNgPYxvJ28lg
 QVpd5RdGWXHo14LWBTD1mtFkCiAhVlATsVNI/tjv2tv7Jp8EsylbDHe7hslA0rns
 Rr2cS9bvpM03AgMBAAGjEzARMA8GA1UdEwEB/wQFMAMBAf8wDQYJKoZIhvcNAQEF
 BQADggEB
 
 
 ADLL/Up63HkFWD15INcW
 Xd1nZGI+gO/whm58ICyJ1Js7ON6N4NyBTwe8513CvdOlOdG/Ctmy2gxEE47HhEed
 ST8AUooI0ey599t84P20gGRuOYIjr7c=
 -END CERTIFICATE-
 
 Broken implementations can successfully verify it using the 
 Starfield Class 2 Certification Authority:
 

I tried to parse and verify this certificate using openssl's asn1parse command. 
However, I get an error:

Error in encoding
7469:error:0D07207B:asn1 encoding routines:ASN1_get_object:header too 
long:asn1_lib.c:150:

I am using openssl version 0.9.8c as of Sep 05, 2006 (Linux/Debian system).

Any ideas what I am doing wrong?

Cheers,
Ulrich


-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: [cryptography] Re: Why the exponent 3 error happened:

2006-09-20 Thread Ralf-Philipp Weinmann


On Sep 20, 2006, at 3:10 PM, Kuehn, Ulrich wrote:


-BEGIN CERTIFICATE-
MIICgzCCAWugAwIBAgIBFzANBgkqhkiG9w0BAQUFADBoMQswCQYDVQQGEwJVUzEl
MCMGA1UEChMcU3RhcmZpZWxkIFRlY2hub2xvZ2llcywgSW5jLjEyMDAGA1UECxMp
U3RhcmZpZWxkIENsYXNzIDIgQ2VydGlmaWNhdGlvbiBBdXRob3JpdHkwHhcNMDYw
ODE5MTY1MTMwWhcNMDYxMDE4MTY1MTMwWjARMQ8wDQYDVQQDEwZIYWNrZXIwgZ8w
DQYJKoZIhvcNAQEBBQADgY0AMIGJAoGBAKSu6ChWttBsOpaBrYf4PzyCGNe6DuE7
rmq4CMskdz8uiAJ3wVd8jGsjdeY4YzoXSVp+9mEF6XqNgyDf8Ub3kNgPYxvJ28lg
QVpd5RdGWXHo14LWBTD1mtFkCiAhVlATsVNI/tjv2tv7Jp8EsylbDHe7hslA0rns
Rr2cS9bvpM03AgMBAAGjEzARMA8GA1UdEwEB/wQFMAMBAf8wDQYJKoZIhvcNAQEF
BQADggEB


ADLL/Up63HkFWD15INcW
Xd1nZGI+gO/whm58ICyJ1Js7ON6N4NyBTwe8513CvdOlOdG/Ctmy2gxEE47HhEed
ST8AUooI0ey599t84P20gGRuOYIjr7c=
-END CERTIFICATE-

Broken implementations can successfully verify it using the
Starfield Class 2 Certification Authority:



I tried to parse and verify this certificate using openssl's  
asn1parse command. However, I get an error:


Error in encoding
7469:error:0D07207B:asn1 encoding routines:ASN1_get_object:header  
too long:asn1_lib.c:150:


I am using openssl version 0.9.8c as of Sep 05, 2006 (Linux/Debian  
system).


Hi Ulrich,

You're using a version that has already been fixed. However the main  
problem seems to be that you're trying to parse a certificate in PEM  
format using the option -inform DER instead of -inform PEM ;)


At least that's how I can reproduce your error...

Cheers,
Ralf



smime.p7s
Description: S/MIME cryptographic signature


Did Hezbollah use SIGINT against Israel?

2006-09-20 Thread Steven M. Bellovin
http://www.newsday.com/news/printedition/stories/ny-wocode184896831sep18,0,7091966,print.story

That isn't supposed to be possible these days...  (I regard it as more
likely that they were doing traffic analysis and direction-finding than
actually cracking the ciphers.)

--Steven M. Bellovin, http://www.cs.columbia.edu/~smb

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Exponent 3 damage spreads...

2006-09-20 Thread Peter Gutmann
David Wagner [EMAIL PROTECTED] writes:

(a) Any implementation that doesn't check whether there is extra junk left
over after the hash digest isn't implementing the PKCS#1.5 standard
correctly. That's a bug in the implementation.

No, it's a bug in the spec:

9.4 Encryption-block parsing

It is an error if any of the following conditions occurs:

 oThe encryption block EB cannot be parsed
  unambiguously (see notes to Section 8.1).
  
 oThe padding string PS consists of fewer than eight
  octets, or is inconsistent with the block type BT.
  
 oThe decryption process is a public-key operation
  and the block type BT is not 00 or 01, or the
  decryption process is a private-key operation and
  the block type is not 02.

Nothing in there about trailing garbage.

Someone else said that the spec requires creating an encoded form of the ASN.1
data and then comparing the encoded form.  Let's look at the spec again:

10.2.3 Data decoding

The data D shall be BER-decoded to give an ASN.1 value of type DigestInfo,
which shall be separated into a message digest MD and a message-digest
algorithm identifier. The message-digest algorithm identifier shall determine
the selected message-digest algorithm for the next step.

Again, there's nothing in there that requires comparing the encoded form.

You may be wondering why this differs somewhat from RFC 3447.  That's because
this is the original gold standard PKCS #1 spec, the one that everyone was
using when PGP, PKCS #7/S/MIME, SSL, and possibly DNSSEC were created.  True,
since then other variants of the spec have imposed slightly different
requirements, but the gold standard version that's contemporaneous with the
security protocols in which it's caused problems doesn't require the measures
that people have been claiming.

(And I really, *really* don't want to get into some pointless debate over
whose bits are more standards-compliant.  All I'm pointing out is that a
blanket assertion that doing/not doing X is a violation of the spec is an
invalid claim.  At best you can say doing X is a violation of one variant of
the spec that didn't actually exist when the affected protocols were
created).

If your implementation supports appending additional parameter fields of some
general structure, then you have not implemented conventional PKCS#1.5
signatures as they are usually understood; instead, you have implemented some
extension. 

No, you've implemented PKCS #1 exactly as the specification says.  Look up
the definition of AlgorithmIdentifier.

Why are people still deploying cryptographic schemes that haven't been
properly validated?

Because everyone else on the planet is doing it, and (with a few caveats) it's
worked so far.  If you're quite happy to not be able to talk to anything else
in existence, you're welcome to use PSS or whatever's in fashion at the
moment.  Since my users expect to be able to, you know, talk to one another,
I'll stick with PKCS #1.

Consequently, I think the focus on e=3 is misguided. 

It's not at all misguided.  This whole debate about trying to hang on to e=3
seems like the argument about epicycles, you modify the theory to handle
anomalies, then you modify it again to handle further anomalies, then you
modify it again, and again, ...  Alternatively, you say that the earth
revolves around the sun, and all of the kludges upon kludges go away.
Similarly, the thousands of words of nitpicking standards, bashing ASN.1, and
so on ad nauseum, can be eliminated entirely by following one simple rule:

  Don't use e=3

This is never going to be reliably fixed if the fix is to assume that every
implementor and implementation everywhere can get every miniscule detail right
every time.  The fix is to stop using e=3 and be done with it.  Even Microsoft
finally got this message after 14 years of getting RC4 wrong, they simply
banned its use because they realised that they'd never get it fixed even if,
in theory, it's easy to get right on paper.

Peter.

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


fyi: On-card displays

2006-09-20 Thread Jeff . Hodges
From: Ian Brown [EMAIL PROTECTED]
Subject: On-card displays
To: [EMAIL PROTECTED]
Date: Wed, 20 Sep 2006 07:29:13 +0100


Via Bruce Schneier's blog, flexible displays that can sit on smartcards.
So we finally have an output mechanism that means you don't have to
trust smartcard terminal displays:
http://www.cr80news.com/library/2006/09/16/on-card-displays-become-reality-maki
ng-cards-more-secure/

So, when do we see the combined chip/fingerprint reader/display on a
payment card :) Doesn't of course address the requirement that we want
evidence (such as a signed paper receipt) that can later be adjudicated
by a court with higher evidential standards than a bank statement that
their systems work perfectly...
- -- 
Blogzilla -- http://dooom.blogspot.com/


--

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]