Re: Exponent 3 damage spreads...

[Steven M. Bellovin]

On Thu, 21 Sep 2006 07:00:03 -0400, "Whyte, William" <[EMAIL PROTECTED]>
wrote:

> > 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
> 
> I'd extend it to "don't use e <= 17". The PKCS#1 attack will work with
> e = 17, SHA-512 and RSA-15360, and someone's bound to implement RSA-15360
> somewhere to claim 256-bit security.


NIST's draft revision of FIPS 186-3 says

   (b) The exponent e shall be an odd positive integer such that
   65,537 <= e < 2**(nlen - 2*security_strength)
   where nlen is the length of the modulus n in bits.

The security_strength is the work factor for brute force attack on the
corresponding symmetric cipher or hash function, i.e., 128 for SHA-256.


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

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

Call for papers for Fast Software Encryption (FSE 2007)

[FSE 2007 Information]

   Fast Software Encryption 2007

*March 26-28*

*Luxembourg city**, Luxembourg**
*

[image: IACR] 

 Call for Papers

FSE 2007 is the 14th annual Fast Software Encryption workshop, for the sixth
year sponsored by the International Association for Cryptologic
Research(IACR). Original research papers on
symmetric cryptology are invited for
submission to FSE 2007. The workshop concentrates on fast and secure
primitives for symmetric cryptography, including the design and analysis of
block ciphers, stream ciphers, encryption schemes, hash functions, and
message authentication codes (MACs), analysis and evaluation tools.
Important dates

Submission deadline

December 11, 2006

Notification of decision

January 31, 2007

Pre-proceedings version deadline

February 20, 2007

Workshop

March 26 - 28, 2007

Proceedings version deadline

April 25, 2007
 Instructions for Authors

Submissions *must not substantially duplicate work* that any of the authors
has published elsewhere or has submitted in parallel to any other
international conference or workshop that has proceedings. Double
submissions will be rejected without evaluation.

The submission must be *anonymous*, with no author names, affiliations,
acknowledgments, or obvious references. It should begin with a title, a
short abstract, and a list of keywords. The length of the submission should
be at most 12 pages excluding bibliography and appendices using at least
11pt size font, reasonably sized margins and total of not more than 20
pages. The introduction should summarize the contributions of the paper at a
level appropriate for a non-specialist reader. Committee members are not
required to read appendices; the paper should be intelligible without them.
Submissions not meeting these guidelines risk rejection without
consideration of their merits.

It is strongly preferred that submissions be processed in LaTeX according to
the instructions listed on
http://www.springer.de/comp/lncs/authors.htmlsince these are mandatory
for the final papers. Submitted papers must be in
PDF or postscript format and should be submitted electronically. Detailed
description of the electronic submission procedure will be available via
http://lacs.uni.lu/fse2007/.

Authors of accepted papers must guarantee that their paper will be presented
at the workshop.
Proceedings

Pre-proceedings will be available at the workshop. Proceedings are intended
to be published in Springer-Verlag's Lecture Notes in Computer Science
series. Authors of accepted papers will be required to complete the IACR
copyright assignment form at
http://www.iacr.org/forms/copyright_agreement.html for their work to be
published in the workshop proceedings.
Program Committee

Frederik Armknecht

NEC, Germany

Steve Babbage

Vodafone, U.K.

Alex Biryukov (chair)

University of Luxembourg, Luxembourg

Claude Carlet

INRIA+University of Paris 8, France

Nicolas Courtois

Gemalto, France

Joan Daemen

STMicroelectronics, Belgium

Orr Dunkelman

Technion - Israel Institute of Technology, Israel

Henri Gilbert

France Telecom, France

Louis Granboulan

EADS, France

Helena Handschuh

Spansion, France

Jin Hong

Seoul National University, Korea

Seokhie Hong

CIST, Korea

Tetsu Iwata

Nagoya University, Japan

Thomas Johansson

Lund University, Sweden

Antoine Joux

DGA + University of Versailles, France

Pascal Junod

Nagravision, Switzerland

Charanjit Jutla

IBM Watson, U.S.A.

John Kelsey

NIST, U.S.A.

Lars R. Knudsen

Technical University of Denmark, Denmark

Stefan Lucks

University of Mannheim, Germany

Mitsuru Matsui

Mitsubishi Electric, Japan

Willi Meier

FHMW, Switzerland

Kaisa Nyberg

Nokia and Helsinki University of Technology, Finland

Elisabeth Oswald

Graz University of Technology, Austria

Josef Pieprzyk

Macquarie University, Australia

Bart Preneel

K.U.Leuven, Belgium

Greg Rose

Qualcomm, U.S.A.

Palash Sarkar

Indian Statistical Institute, India

Serge Vaudenay

EPFL, Switzerland
 Workshop Information and Stipends

The primary source of information is http://lacs.uni.lu/fse2007/ but any
remaining questions can be sent to [EMAIL PROTECTED] a limited number
of stipends are available to those unable to obtain funding to attend the
workshop. Students, whose papers are accepted and who will present the paper
themselves, are encouraged to apply if such assistance is needed. Requests
for stipends should be sent to [EMAIL PROTECTED]

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

RE: Exponent 3 damage spreads...

[Peter Gutmann]

"Kuehn, Ulrich" <[EMAIL PROTECTED]> writes:

>   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.
>
>Here, any trailing garbage would be included in data D. But does an ASN.1
>value allow such a thing? I am asking this independently of our discussion
>here.

I don't think it's a problem, you just take the ASN.1 DigestInfo value, since
the trailing garbage isn't part of the DigestInfo, you ignore it.
Specifically, the ASN.1 object is entirely self-contained, so you can tell
exactly where it ends and what it contains.  Anything outside it is beyond the
scope of this specification :-).

(When the spec was written, I think the thought that someone would append
trailing garbage never cropped up, so it's never explicitly addressed).

>Anyway, I think we agree on the point that the spec (even version 2.1) is in
>some point unprecise which should be considered a bug, as it can lead to
>implementation flaws. And yes, given what we know, e=3 is a good candidate
>for elimination :)

Yup :-).

Peter.


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

Re: Exponent 3 damage spreads...

[Simon Josefsson]

[EMAIL PROTECTED] (Peter Gutmann) writes:

>>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.

Not using e=3 when generating a key seems like an easy sell.

A harder sell might be whether widely deployed implementations such as
TLS should start to reject signatures done with an e=3 RSA key.

What do people think, is there sufficient grounds for actually
_rejecting_ e=3 signatures?

One alternative would be to produce a warning, similar to what is
sometimes done for MD2 and MD5 today.

Btw, by default, OpenSSH's ssh-keygen appear to use e=35 (0x23..),
GnuPG (libgcrypt), GnuTLS and OpenSSL appear to all use e=65537, BIND
dnssec-keygen appear to use e=3.

/Simon

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

Re: Did Hezbollah use SIGINT against Israel?

[Alexander Klimov]

On Wed, 20 Sep 2006, Steven M. Bellovin wrote:
> http://www.newsday.com/news/printedition/stories/ny-wocode184896831sep18,0,7091966,print.story
>
> That isn't supposed to be possible these days...

It is not clear that with modern technology interception is
impossible, at least during Second Gulf War the reports about
SIGINT against US were quite convincing:

 


> (I regard it as more
> likely that they were doing traffic analysis and direction-finding than
> actually cracking the ciphers.)

IIUC, spread-spectrum communication is not much stronger than the
background noise, and thus the traffic analysis is not that easy
either.

My guess that at least some information was leaked due to cellular
phones (the solders were routinely calling their families).

"Besides radio transmissions, the official said Hezbollah also
 monitored cell phone calls among Israeli troops. But cell phones are
 usually easier to intercept than military radio, and officials said
 Israeli forces were under strict orders not to divulge sensitive
 information over the phone."

Even if one don't care what was said over the phone, a lot of
information can be extracted from mere location of a phone
(especially, if one knows the owner of each phone):

"Israeli officials said the base also had detailed maps of northern
 Israel, lists of Israeli patrols along the border and cell phone
 numbers for Israeli commanders."

-- 
Regards,
ASK

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

Re: Why the exponent 3 error happened:

[Anton Stiglic]

As other's have mentioned, I don't believe the small RSA exponent (e = 3)
is to blame in Bleichenbacher's attack.
Indeed, the mathematical problem of computing the cubic root of m modulo
an rsa modulus n, for a *fixed*, arbitrary m, is still considered to be
hard (no one has shown the opposite).
What Bleichenbacher demonstrated is that computing the cubic root of m' ||
G, where G can be any value, garbage, and is sufficiently large, is easy.

These are two different problems, and the vulnerability is due to the fact
that these libraries allow for the variant G part.

I don't see ASN.1 as being faulty either.  The ASN.1 simply acts as a
value that allows you to determine what hash algorithm to use.  If the
encrypted signature would be of the form:
  What-ever-padding, hash, header
and implementations would directly go to the least significant bits in
order to retrieve the header (which should be of fixed size), and then
retrieve the hash, we wouldn't have this problem.

I believe you should put the most sensitive information in the least
significant bytes, which are harder to manipulate (Bleichenbacher's attack
plays with the most significant bytes, the least significant bytes are
basically random in his calculations, he doesn't have control over them).

This reminds me of the RSA lsb hardness problem theorem
http://www.wisdom.weizmann.ac.il/~oded/annot/node17.html
I have notes explaining it right here, section 8.4.1:
http://crypto.cs.mcgill.ca/~stiglic/Papers/crypto2.ps
The theorem basically says that if you can predict the least significant
bit of the plaintext given the corresponding RSA ciphertext, than you can
compute the whole plaintext.
The theorem doesn't directly apply however (RSA signature verification
uses the encryption operation, not decryption), but may be of some
insight.

The problem is that we (crypto community) still don't have a good way of
writing specs.  This is in fact a hard problem.  And the problem doesn't
get easier with the increasing complexity of the specs.  We need simple
algorithms and protocols, which allow just enough flexibility, and we need
a good and precise way to write specs for these.

On one side you have theoretical cryptographers / mathematicians who work
in an abstract level, develop algorithms and protocols, but don’t have
much interest in implementing these other than possibly in a prototype
form.  On the other end, you have developers who excel in coding and
system integration but don’t necessarily understand the theoretical
background in all its details.  Specifications act as a bridge between
these two worlds, but this bridge is not very solid today.  We need to do
allot more effort into building stronger bridges.

--Anton


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

RE: Exponent 3 damage spreads...

[Anton Stiglic]

Thanks for taking the time to look at this.

But I recounted, and I count 765 hex (with the formatting I get in my mail,
11 lines of 68 hex + 17 hex at the end), which gives 3060 bits.  Considering
that the first hex is 1 and can be represented in 1 bit, not for, that would
give 3060 - 3 = 3057 bits.

The modulus is the same size, but starts with 1D instead of 1F (the
beginning of s^3), so s^3 is bigger.  My bc library has a function called
bits which returns the number of bits, I get 3057 in both cases, see bellow
(also look at the value of m - s, which is negative, and modexp(s, 3, m)
which doesn't have the form we want, but modexp(s/100, 3, m) does).  

But I seem to remember now that in openssl, mod(x, y) doesn't always return
a value which is between 0 and y, maybe it would accept my s.  Will try it.

--Anton

m
1D851D5148345606F586935D227CD5CF7F04F890AC5024178BA5F4EE85D7796918C3\
DC7A5951C985539CB240E28BA4AC3AFBE0F6EB3151A0DBAFD686C234A30D07D590D6\
1A5474491BF0D68E1AC7F94CDC989C19C2E25B12511A29FFAF5F11E0B994E19C5C3D\
C298F9E584FFF3C7DBB8F703A0EAD97167F88C7229BBFA55B449CDE4C91B409D5B9A\
CF0134CB61352E9CE6CB3D847C7F3D9AFA74E8E19DD1ED7923270E310A5D91E97EF1\
98694465950715AA066ACB06FAEC0BA64FCCCA155104852EFD41346F75D1ACB8574B\
BE3C7C8D6D1B501C1163AD2058506DF1B64059A6932C0672FB9D094364EA4D7FA044\
42B8E643B74B8746B594866C7CBDAB8FEA954FDEE7C44B9C5D6B9E19B49082D65B51\
7EA7DBFEF5CA1EEA39AB2283CDB854C8B246F2B8EFE51895349640248A3248EC65F6\
4A89CA5AB194B444DF676B015AFBCACE13697CEEB5268F5E9AA674A83DD1B0CE4DC8\
3603CFFB801DB669216FC647CD7A6A84831E421D9676C7AAC44411B2AB3E901A7139\
B3519B58EBAEEC20B
s
7FFF\
\
FFEAAEAD6EAB6B2B18EBD595822B1555\
AC5D20CF08046814578C2B994E1DBD8413A43C05640
bits(m)
BF1
bits(s^3)
BF1
m - s^3
-27AE2AEB7CBA9F90A796CA2DD832A3080FB076F53AFDBE8745A0B117A288696E73C\
2385A6AE367AAC634DBF1D745B53C5041F0914CEAE5F245029793DCB5CF2F82A6F29\
E5AB8BB6E40F2971E53806B3236763E63D1DA4DDB1E7E900E10140D0269B4003F3C2\
7EACDEB5C1035A4765F029AF59AB74B1A6C2A091E14405AA4BB6321B36E4BF62A465\
30FECB349ECAD1631934C27B8380C265058B171E622E1286DCD8F1CEF5A26E16810E\
6796BB9A6DA29467C54B41AC61C95E3785A9F85D4578F21C056D03ECF9128580717D\
563B5F437FEB9CDCAAE7E01D6C84F908AF5336EC3D710D6DF1F282A270E150F32438\
31826C7843300F514A6B799383425470156AB021183BB4637CBCB87B1902C4D519D7\
52B7C10EC94263DF2E26A5466F17150A2E4E2745BD967E5CC8352D58EE7A5237E637\
3B36C59357EE1C3BCBBAE5A3EBFA812347B2D71FF03ECAD84A80E22419EA004D6C73\
4BD35CE67B61094E6292B8E8BA5005F3D0F436A6C0EE1F47EDAFD37F94C16FE58EC6\
4CAE64A7145113DF5

modexp(s, 3, m)
27AE2AEB7CBA9F90A796CA2DD832A3080FB076F53AFDBE8745A0B117A288696E73C2\
385A6AE367AAC634DBF1D745B53C5041F0914CEAE5F245029793DCB5CF2F82A6F29E\
5AB8BB6E40F2971E53806B3236763E63D1DA4DDB1E7E900E10140D0269B4003F3C27\
EACDEB5C1035A4765F029AF59AB74B1A6C2A091E14405AA4BB6321B36E4BF62A4653\
0FECB349ECAD1631934C27B8380C265058B171E622E1286DCD8F1CEF5A26E16810E6\
796BB9A6DA29467C54B41AC61C95E3785A9F85D4578F21C056D03ECF9128580717D5\
63B5F437FEB9CDCAAE7E01D6C84F908AF5336EC3D710D6DF1F282A270E150F324383\
1826C7843300F514A6B799383425470156AB021183BB4637CBCB87B1902C4D519D75\
2B7C10EC94263DF2E26A5466F17150A2E4E2745BD967E5CC8352D58EE7A5237E6373\
B36C59357EE1C3BCBBAE5A3EBFA812347B2D71FF03ECAD84A80E22419EA004D6C734\
BD35CE67B61094E6292B8E8BA5005F3D0F436A6C0EE1F47EDAFD37F94C16FE58EC64\
CAE64A7145113DF5
modexp(s/100, 3, m)
1FFF\
\
FFF003021300906052B0E03021A05000\
4145D89B46034E0F41A920B2FA964E230EBB2D040B00\
\
02A9AA11CBB60CB35CB569DDD576C272967D774B02AE385C6EE43238C8C9\
1477DBD0ED06ECF8BC4B8D3DC4D566FA65939092D09D13E0ED8F8BE5D5CB9E72C47C\
743B52BBFA7B9697DA285694CD9347AB7528\
D15F9D0DBF0C82C967D1C7CA3CCF69D2E09519FEAD7B96F1FCCB6D7D78AC9B244C2D\
85C08FEE0982D080AB2250A546F64BF15B1C540EA5655A36E52756CC57BBB11BBA3B\
81D72CE1FB7EBFB784027F3087CA7078541278C45764E6F2B1F3E5324000\
000



-Original Message-
From: "Hal Finney" [mailto:[EMAIL PROTECTED] 
Sent: September 20, 2006 6:21 PM
To: [EMAIL PROTECTED]; cryptography@metzdowd.com
Subject: RE: Exponent 3 damage spreads...

Anton Stiglic writes:
> I tried coming up with my own forged signature that could be validated
with
> OpenSSL (which I intended to use to test other libraries). ...

> Now let's look at s^3
> 1FFF\
> \
> FFF003021300906052B0E03021A05000\
> 4145D89B46034E0F41A920B2FA964E230EBB2D040B00\
> 0

RE: Exponent 3 damage spreads...

[Whyte, William]

> 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

I'd extend it to "don't use e <= 17". The PKCS#1 attack will work with
e = 17, SHA-512 and RSA-15360, and someone's bound to implement RSA-15360
somewhere to claim 256-bit security.

William

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

RE: Exponent 3 damage spreads...

[Kuehn, Ulrich]

Peter, 

> From: Peter Gutmann [mailto:[EMAIL PROTECTED] 
> 
> "Kuehn, Ulrich" <[EMAIL PROTECTED]> writes:
> 
> >But the PKCS#1 spec talks about building up the complete padded 
> >signature input at the verifier, and then comparing it.
> 
> Uhh, did you actually read the rest of my post?  *One variant 
> of the PKCS #1 spec, that didn't exist at the time the the 
> affected other standards were created*, talks about ..., not 
> "the PKCS #1 spec" as a whole.  I even quoted the original 
> text of the spec in my message.
> 

It might have helped if you indicated that the citation was from the PKCS#1 
standard version 1.5 (?).

Interestingly, I find there (version 1.5) also

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.

It is an error if the message-digest algorithm identifier
does not identify the MD2, MD4 or MD5 message-digest
algorithm.

Here, any trailing garbage would be included in data D. But does an ASN.1 value 
allow such a thing? I am asking this independently of our discussion here.


Anyway, I think we agree on the point that the spec (even version 2.1) is in 
some point unprecise which should be considered a bug, as it can lead to 
implementation flaws. And yes, given what we know, e=3 is a good candidate for 
elimination :)

Ulrich

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

RE: Exponent 3 damage spreads...

[Peter Gutmann]

"Kuehn, Ulrich" <[EMAIL PROTECTED]> writes:

>But the PKCS#1 spec talks about building up the complete padded signature
>input at the verifier, and then comparing it.

Uhh, did you actually read the rest of my post?  *One variant of the PKCS #1
spec, that didn't exist at the time the the affected other standards were
created*, talks about ..., not "the PKCS #1 spec" as a whole.  I even quoted
the original text of the spec in my message.

Peter.


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

RE: Exponent 3 damage spreads...

[Kuehn, Ulrich]

Peter,

> From: Peter Gutmann [mailto:[EMAIL PROTECTED] 
> 
> 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
> >
[...]
> 
> Nothing in there about trailing garbage.
> 

Actually, this part is about _encryption_, we are talking here about signature 
padding. But the PKCS#1 spec talks about building up the complete padded 
signature input at the verifier, and then comparing it. However, there is a 
note saying that alternatively one could parse the padding without saying how 
this would be done. The reason to use such a thing is given as saving 
intermediate memory. Oh well!

So in fact what a lot of implementors do, parsing the padding, is not specified 
in sufficient detail to get it right. I would consider this buggy 
implementation resulting from buggy specification.

Regards,
Ulrich

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

Public Key Cryptography 30th Anniversary Event - 10/26, Mountain View CA

[Bill Stewart]

From: "Computer History Museum" <[EMAIL PROTECTED]>
Subject: Public Key Cryptography 30th Anniversary Event - October 26

Celebrating 30 years of Public Key Cryptography (PKC)

Join the Computer History Museum for a special public event celebrating 30
years of public key cryptography. This memorable evening celebration will
honor the inventors, the inventions, the milestones, and the future of PKC.
The program is moderated by Steven Levy, author of Crypto and senior editor
Newsweek, and includes Ray Ozzie, Whitfield Diffie, Martin Hellman, Jim
Bidzos, Dan Boneh, Brian Snow, and John Markoff.  All will share their
opinions on the state of the industry today and an audience question and
answer session will complete the evening.

Go to
www.computerhistory.org/events/PKC/ to register for this exclusive
celebration.  Space is limited, so register
today.

WHERE
~
Computer History Museum
1401 N. Shoreline Blvd.
Mountain View CA 94043
(Highway 101 at Shoreline)

www.computerhistory.org/about/directions/

WHEN
~
OCTOBER 26, 2006
6 to 9 pm

AGENDA
~
6:00 to 7:00 PM
Networking reception

7:00 to 7:30 PM
Welcome and PKC Overview

7:30 to 8:30 PM
Panel presentation

8:30 to 9:00 PM
Audience question and answer session

Please join us on October 26th for this networking reception and panel
presentation. Mark your calendar now, and visit
www.computerhistory.org/events/PKC/ to register for this celebration.

Space is limited, so register today.



s p o n s o r e d  b y  Voltage Security and RSA:
www.voltagesecurity.com
www.rsasecurity.com



You are currently part of the Lecture announcement list of the Computer
History Museum. To unsubscribe, please reply to this message with the word
"remove" in the subject line.
--

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

RE: Exponent 3 damage spreads...

[Tolga Acar]

 Anton,

Here is what I compute in Maple.
I wonder if you are running into an old BC bug. I don't remember the
details, but bc had a bug some 10 years or so ago with big numbers.

> with(numtheory):
>
s:=convert(`00D3CDA91B578B6DF29AEB140272BD9198759F79FA10DC410B5D10362048AC7A
BE5DF7FE0D94A6646E791C5B95B29F2C6384A570769DC888ED0B7AD510CCD3C758CEBEB64851
1620490E0FD54162BADB1ED05411ACC853509B62A4C1B242E1E2F737A1E7E4340F5A79B05EC3
475D7BA6FC7B3302F1258ABAC1079F11E8DFB9FC09D42716BA4054ADD460BB12FC1B0B8D5D32
DB50395374AEB3C215C2BC566328D2F03BF043068C5C9ABC649BA1767E97DF32B6AA734594EE
22FFFE7FB06EA3B77030E79BD6FE7683AB7FFCE462ABFBA5777B3914DE4665B86C1EC203FEB6
FCCB3DADB8BA51FD87A7457C62385418E65D17809C4256E3D27DC2017D7A093C8BD193A09168
F34D522DD7D3AFB95FC61C9F4339091CF25D78BF461B4EA5620EED722AB7D3EFF99CEA4A4F54
6BFF6CE338D7763AFF20A9B61452DA07179590D3316BBCE63B06B43D996D775D6843F46633FF
107A3C866E3B0A8AAAEA31F4A2048C9FCB448958287F8E961C9F3393E18FC9A05460D51A2867
37AEC14A1A7B27A51`,decimal,hex):
>
m:=convert(`01D851D5148345606F586935D227CD5CF7F04F890AC5024178BA5F4EE85D7796
918C3DC7A5951C985539CB240E28BA4AC3AFBE0F6EB3151A0DBAFD686C234A30D07D590D61A5
474491BF0D68E1AC7F94CDC989C19C2E25B12511A29FFAF5F11E0B994E19C5C3DC298F9E584F
FF3C7DBB8F703A0EAD97167F88C7229BBFA55B449CDE4C91B409D5B9ACF0134CB61352E9CE6C
B3D847C7F3D9AFA74E8E19DD1ED7923270E310A5D91E97EF198694465950715AA066ACB06FAE
C0BA64FCCCA155104852EFD41346F75D1ACB8574BBE3C7C8D6D1B501C1163AD2058506DF1B64
059A6932C0672FB9D094364EA4D7FA04442B8E643B74B8746B594866C7CBDAB8FEA954FDEE7C
44B9C5D6B9E19B49082D65B517EA7DBFEF5CA1EEA39AB2283CDB854C8B246F2B8EFE51895349
640248A3248EC65F64A89CA5AB194B444DF676B015AFBCACE13697CEEB5268F5E9AA674A83DD
1B0CE4DC83603CFFB801DB669216FC647CD7A6A84831E421D9676C7AAC44411B2AB3E901A713
9B3519B58EBAEEC20B`,decimal,hex):
> c:=s&^3 mod m:
> convert(c,hex);
> 

1B5FD52F9033ADD581101429F83B600AB9280AF9F448FCAF1F8F3D1375D526A390\
B949DE72773778D4C4C1A517730A90BA1DDC5DAEACE248534B1ECBF53B8957\
E595A8097D6828E1D05E9B7207EAA8425CC54365D78AEC13A53713AA6B44E5\
E63860824D0748184208398611253CC08E2AACE1ED62FDEB85403507512F90\
296CEC26A05194C1332792468AC83D8411F4A1609799F7AAE9E60C84B33EDB\
E4CD590D58A5483A9A94B52853E7CF81DBFEECCD922AB1D954F9FEA40C22BB\
575A094730F9F2AE5ECDD023AB37740984F5289F2C3900512974BE878D1A8D\
D880A871BEF9FE3C18A28DA9A40ABFF0B1288DFC9BA6971883E7263500BACC\
458E3F9D1847BE6D542948363E8544BC2E7890580063D322DA203172FADA62\
B8D42A7959DA60CB6DC5CB90DB9E3F046F2AE816524FF5D112EB2CAC0E7D96\
365550E68EAEA1EB2C17E63EC51719F4299A7FF68DD544FD2A6639F9B991F7\
9F4497EAF86EA7E8964B28125772414BDA2369EA39994D972B863C2E46072D\
56CEFF7E54A5774F1

> c2:=m&^3 mod s:
> convert(c2,hex);

89DB60414C5FE1762638AE4C61C0B485812C50E711FD7EAFA34544208E4E110F2A\
04EDCF5CD2A71F13EC1640606DB7A49F6FD15E91269D5FF325FD6ECA6E\
80FFDD9DC196E199DA55D69259E6022910598A886A4AFDC196C641B5BFF9C6\
18D5EC1429C669D37C6A9B64EFDDF146C1774261B7CC9D53D360AC0B072546\
568699A354E85BACA05119C09C5EE92A05B8AFE4BDBD725171A19F687AFE8B\
B28000181201CD7534C7D2A62B53796173BCA080630212CDD60D92A4E00E14\
446748873F05AF14DBDECD5B5143F01C26A91A510623926DAADEADA8E16D6F\
52C4184035767A2109197147D2279CDA312897CD346B5C8D0C7BFAE33CE33C\
C7C94E7C2CD66B212D99ADC15373E9815893F44B9510140395DB5EAC436E09\
71E9D05EF760E477B58713B770A3FE61E37B2456543D8865D3272CC89F7390\
03770446F4FD6CACA14BDCD7C5050774516C77456958BAF794ADE9A8BDB8A4\
9092631DD467B0158BFBA416164D81DC8DE5C9D75118DA5BDB0CB121DC0C11\
5271451781B4D0F

> 

> -Original Message-
> From: [EMAIL PROTECTED] 
> [mailto:[EMAIL PROTECTED] On Behalf Of Anton Stiglic
> Sent: Tuesday, September 19, 2006 8:56 PM
> To: cryptography@metzdowd.com
> Cc: 'Anton Stiglic'
> Subject: RE: Exponent 3 damage spreads...
> 
> 
> 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

RE: Exponent 3 damage spreads...

["Hal Finney"]

Anton Stiglic writes:
> I tried coming up with my own forged signature that could be validated with
> OpenSSL (which I intended to use to test other libraries). ...

> Now let's look at s^3
> 1FFF\
> \
> FFF003021300906052B0E03021A05000\
> 4145D89B46034E0F41A920B2FA964E230EBB2D040B00\
> \
> 02A9AA11CBB60CB35CB569DDD576C272967D774B02AE385C6EE43238C8C9\
> 1477DBD0ED06ECF8BC4B8D3DC4D566FA65939092D09D13E0ED8F8BE5D5CB9E72C47C\
> 743B52BBFA7B9697DA285694CD9347AB7528\
> D15F9D0DBF0C82C967D1C7CA3CCF69D2E09519FEAD7B96F1FCCB6D7D78AC9B244C2D\
> 85C08FEE0982D080AB2250A546F64BF15B1C540EA5655A36E52756CC57BBB11BBA3B\
> 81D72CE1FB7EBFB784027F3087CA7078541278C45764E6F2B1F3E5324000\
> 0
>
> 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.
>
> Only one problem, s^3 is larger than m, so if we computed modexp(s, 3, m)
> the result would be rounded out modulo m and we would loose the above
> structure.

This is not correct.  I counted, and the number shown above has 762
hex digits.  It is 3057 bits long, compared to m which is 3072 bits.
It is not bigger than m, and does not need to be adjusted.  3057 is
precisely the correct number of bits for a PKCS-1 padded value for a
3072 bit exponent.

Hal

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

Re: Did Hezbollah use SIGINT against Israel?

[Leichter, Jerry]

| 
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.)
Newspaper reports have claimed that many troops were sent into the
field with old equipment - including in particular 10+-year-old
communications equipment.  Something that was fielded in 1996 was
likely designed using the technology of the early '90's.  Portable
communications equipment built with that technology is probably not
secure today.
-- Jerry


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

Re: fyi: On-card displays

[Steve Schear]

At 02:45 PM 9/20/2006, [EMAIL PROTECTED] wrote:

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/


I have a Mondex card from years ago that used a separate reader with LCD.

Steve 



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