Re: 2048 bits, damn the electrons! [...@openssl.org: [openssl.org #2354] [PATCH] Increase Default RSA Key Size to 2048-bits]

[James Muir]

On 10-09-30 11:41 AM, Thor Lancelot Simon wrote:
> On Wed, Sep 29, 2010 at 09:22:38PM -0700, Chris Palmer wrote:
>> Thor Lancelot Simon writes:
>>
>>> a significant net loss of security, since the huge increase in computation
>>> required will delay or prevent the deployment of "SSL everywhere".
>>
>> That would only happen if we (as security experts) allowed web developers to
>> believe that the speed of RSA is the limiting factor for web application
>> performance.
> 
> At 1024 bits, it is not.  But you are looking at a factor of *9* increase
> in computational cost when you go immediately to 2048 bits.  At that point,
> the bottleneck for many applications shifts, particularly those which are
> served by offload engines specifically to move the bottleneck so it's not
> RSA in the first place.

It sounds like a good time to switch to 224-bit ECC.  You could even use
256-bit ECC, which is comparable to 3072-bit RSA (according to the table
on page 5 of the SEC 2 document).

-James



signature.asc
Description: OpenPGP digital signature

copy of "On the generation of DSS one-time keys"?

[James Muir]

Daniel Bleichenbacher presented an implementation attack against DSA in
2001 titled "On the generation of DSS one-time keys".  I think it made
the rounds as a preprint, but I don't know if it was ever officially
published.  It's cited frequently (e.g. in the SEC1 doc
http://www.secg.org/download/aid-780/sec1-v2.pdf), but I cannot seem to
locate a copy.

Can anyone point me to a copy of this preprint?

-James



signature.asc
Description: OpenPGP digital signature

Re: 1024 bit RSA cracked?

[James Muir]

>> "The RSA algorithm gives security under the assumption that as long as
>> the private key is private, you can't break in unless you guess it.
>> We've shown that that's not true," said Valeria Bertacco, an associate
>> professor in the Department of Electrical Engineering and Computer
>> Science, in a statement.
> 
> They're not the first ones to show that!  Side-channel attacks have been
> around for a while now.  It's not just the algorithms, but the machine
> executing them and its physical characteristics that matter.

I agree. I think the paper overstates its novelty and implications.  It
seems to be an experimental implementation of a fault attack presented
by Boneh, DeMillo and Lipton (i.e. where it is assumed that single bit
errors affect the private exponent).  They target _some_ crypto
application** that uses the openssl library running on an fpga board.
Getting the attack to work in real life is no small feat, so they
deserve props for that, but they make a few questionable claims -- e.g.
they seem to state that the left-to-right fixed-window exponentiation
algorithm was thought to be immune to fault attacks.  In fact, adapting
the BDL attack, which was presented against a right-to-left algorithm,
to work against a left-to-right algorithm is straightforward, and so the
susceptibility of the left-to-right FWE algorithm has been known for
some time.

What I find much more strange about the paper is that the authors make
no mention of message blinding.  I could be wrong, but message blinding
would defeat their attack.  By default, an openssl server utilizes
message blinding in its private key operations, so there attack wouldn't
apply...

** I just had the following realization:  I had assumed that the authors
were attacking an openssl *server* running on the fpga board, but
perhaps that is not so.  They don't seem to make that specific claim.
They claim only to be attacking an "unmodified version of the OpenSSL
library".  It is possible that they only created a toy RSA application
that generates signatures using the openssl library (i.e. by making
calls to specific openssl functions).  This would explain why they don't
discuss message blinding -- because they didn't enable it in their toy
application!  I suspect that's what they did.  In that case, their
experimental results say very little about the susceptibility of an
openssl server to fault attacks.  Wow... if I'm correct, then the
authors really need to be more clear about exactly what they did.

-James



signature.asc
Description: OpenPGP digital signature

Re: padding attack vs. PKCS7

[James Muir]

travis+ml-cryptogra...@subspacefield.org wrote:
> http://www.matasano.com/log/1749/typing-the-letters-a-e-s-into-your-code-youre-doing-it-wrong/
> 
> Towards the end of this rather offbeat blog post they describe a
> rather clever attack which is possible when the application provides
> error messages (i.e. is an error oracle) for PKCS7 padding in e.g. AES
> CBC-encrypted web authenticators that allows an adversary to attack
> the crypto one octet at a time.

I think this attack can be attributed to Klima and Rosa:

Side Channel Attacks on CBC Encrypted Messages in the PKCS#7 Format.
V. Klima and T. Rosa.
http://eprint.iacr.org/2003/098.pdf

-James



signature.asc
Description: OpenPGP digital signature

Re: white-box crypto Was: consulting question....

[James Muir]

Alexander Klimov wrote:
> On Tue, 26 May 2009, James Muir wrote:
>> There is some academic work on how to protect crypto in software from
>> reverse engineering.  Look-up "white-box cryptography".
>>
>> Disclosure:  the company I work for does white-box crypto.
> 
> Could you explain what is the point of "white-box cryptography" (even
> if it were possible)?

The introduction to the following paper (from SAC 2002) gives a very
good overview of white-box crypto:

http://www.scs.carleton.ca/%7Epaulv/papers/whiteaes.lncs.ps

> If I understand correctly, the only plausible result is to be able to
> use the secret key cryptography as if it were the public-key one, for
> example, to have a program that can do (very slow, btw) AES
> encryption, but be unable to deduce the key (unable to decrypt). If
> this is the case, then why not use normal public-key crypto (baksheesh
> aside)?

You're right -- a white-box implementation of a symmetric cipher
essentially creates an asymmetric cipher.  Despite this, there are still
situations where you might want a whitebox AES implementation running on
a client.  Consider a server that sends out updates to several hundred
clients (each client has its own key).  The clients are subject to
whitebox attacks but the server is not.  Rather than force the server to
do several hundred public-key operations when it needs to push out an
update, we might be able to save the server some work if use a symmetric
cipher.

-James




signature.asc
Description: OpenPGP digital signature

Re: consulting question....

[James Muir]

Ray Dillinger wrote:
> Does anyone feel that I have said anything untrue?
>
> Can anyone point me at good information uses I can use to help prove
> the case to a bunch of skeptics who are considering throwing away
> their hard-earned money on a scheme that, in light of security
> experience, seems foolish?

Security is relative -- you need to evaluate it against a threat model
and consider what goals you are trying to achieve.  A software solution
may succeed in deterring attackers from developing a way to strip the
DRM from a $0.99 mp3; if the mp3 only costs $0.99, then may be it isn't
worth the trouble of reverse engineering the software.

There is some academic work on how to protect crypto in software from
reverse engineering.  Look-up "white-box cryptography".

Disclosure:  the company I work for does white-box crypto.

-James




signature.asc
Description: OpenPGP digital signature

no warrant required

[James Muir]

From today's (13 Feb 2009) National Post:

http://www.nationalpost.com/news/story.html?id=1283120

excerpt:

> An Ontario Superior Court ruling could open the door to police
> routinely using Internet Protocol addresses to find out the names of
> people online, without any need for a search warrant.
> 
> Justice Lynne Leitch found that there is "no reasonable expectation
> of privacy" in subscriber information kept by Internet service
> providers (ISPs), in a decision issued earlier this week.

-James





signature.asc
Description: OpenPGP digital signature

Re: "Cube" cryptanalysis?

[James Muir]

Paul Hoffman wrote:
> At 11:08 AM -0700 8/21/08, Greg Rose wrote:
>> Adi mentioned that the slides and paper will go online around the
>> deadline for Eurocrypt submission; it will all become much clearer
>> than my wounded explanations then.
>
> There now: 
>

Given all the excitement over the Cube attack, readers may be interested
to have a closer look at an earlier paper by Vielhaber:

Breaking ONE.FIVIUM by AIDA (an Algebraic IV Differential Attack)
Michael Vielhaber
http://eprint.iacr.org/2007/413

Vielhaber claims that AIDA anticipates the Cube attack; see his post on
the iacr eprint forum:

http://eprint.iacr.org/forum/read.php?8,59

-James

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

Re: "Cube" cryptanalysis?

[James Muir]

Paul Hoffman wrote:

At 11:08 AM -0700 8/21/08, Greg Rose wrote:
Adi mentioned that the slides and paper will go online around the 
deadline for Eurocrypt submission; it will all become much clearer 
than my wounded explanations then.


There now: 



Given all the excitement over the Cube attack, readers may be interested 
to have a closer look at an earlier paper by Vielhaber:


Breaking ONE.FIVIUM by AIDA (an Algebraic IV Differential Attack)
Michael Vielhaber
http://eprint.iacr.org/2007/413

Vielhaber claims that AIDA anticipates the Cube attack; see his post on 
the iacr eprint forum:


http://eprint.iacr.org/forum/read.php?8,59

-James

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

Re: "Cube" cryptanalysis?

[James Muir]

Paul Hoffman wrote:

At 11:08 AM -0700 8/21/08, Greg Rose wrote:
Adi mentioned that the slides and paper will go online around the 
deadline for Eurocrypt submission; it will all become much clearer 
than my wounded explanations then.


There now: 



I just noticed the following comment from Michael Vielhaber on the iacr 
eprint discussion forum:


http://eprint.iacr.org/forum/read.php?8,59

Vielhaber states that the cube attack is anticipated by his 2007 paper:

Breaking ONE.FIVIUM by AIDA an Algebraic IV Differential Attack
Michael Vielhaber
http://eprint.iacr.org/2007/413

-James

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

Re: "Cube" cryptanalysis?

[James Muir]

Greg Rose wrote:
Basically, any calculation with inputs and outputs can be represented as 
 an (insanely complicated and probably intractable) set of binary 
multivariate polynomials. So long as the degree of the polynomials is 
not too large, the method allows most of the nonlinear terms to be 
cancelled out, even though the attacker can't possibly handle them. Then 
you solve a tractable system of linear equations to recover key (or 
state) bits.


I would like to know how Dinur and Shamir's work differs from Courtois' 
previous work on Algebraic cryptanalysis of block ciphers.  It is a 
refinement of Courtois' technique?  Greg, do you, or someone else have 
some insight on this?


-James

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

Re: Ransomware

[James Muir]

Marcos el Ruptor wrote:

I've just looked at the virus.


Just curious -- where were you able to download the virus from?

-James

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

Re: A call for aid in cracking a 1024-bit malware key

[James Muir]

Steven M. Bellovin wrote:

According to
http://www.computerworld.com/action/article.do?command=viewArticleBasic&articleId=9094818&intsrc=hm_list%3E%20&articleId=9094818&intsrc=hm_list
some new malware is encrypting files with a 1024-bit RSA key.  Victims
are "asked" to pay a random to get their files decrypted.  So -- can
the key be factored?


I saw a similar story reported on Slashdot a few days ago.  I wonder if 
the malware authors cited Adam Young and Moti Yung?  They hypothesized 
about such malware a few years ago:


http://en.wikipedia.org/wiki/Cryptovirology

-James

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

Re: Estimated 10 million dollars lost in parking meter fraud

[James Muir]

michael taylor wrote:



The city is playing a $10M game of catchup to stymie thieves using
bogus credit cards to get free parking


An assuming read. The article mentions the "Europark Card"; you buy it 
online for $15 (the web site is still up) and it gets you free parking 
in various cities in Australia, US, and Canada.  Here is a link to a 
demo video on YouTube:


http://www.youtube.com/watch?v=WfoWDQUR4sk

Unlike the recent Oyster Card crack (London, UK), Toronto's "free" 
parking problem does not seem to have been caused by bad cryptography -- 
at least, there is no mention of cryptography in the article.  It goes 
to show that there's more to systems security than just crypto.


-James

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

Re: fyi: Adi Shamir's microprocessor bug attack

[James Muir]

James A. Donald wrote:

James Muir wrote:
 > Can anyone think of a deployed implementation of RSA
 > signatures that would be vulnerable to the attack
 > Shamir mentions?  Hashing and message blinding would
 > seem to thwart it.

As I said, public key encryption has long been known to
be weak against chosen plaintext and chosen cryptotext -
so protocols have long been designed to prevent this
sort of attack.  If they are not so designed, they were
known to be weak before this attack was discovered.


I completely agree with you.  Good public key cryptography should be
designed to resist chosen message attacks.  This has been a standard
part of cryptographic theory since the 80s.  But this is an
implementation attack, and real world implementations don't necessarily
follow all the rules of cryptographic theory.

If you or anyone else happened to know of a single real-world
implementation of RSA signatures that is vulnerable to this fault
attack, then that might give some justification for the incredible media
coverage it has received.  I can't think of any, and my feeling is that
this announcement has been over-hyped (and presented without proper
perspective).

-James


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

Re: fyi: Adi Shamir's microprocessor bug attack

[James Muir]

' =JeffH ' wrote:

From: John Young <[EMAIL PROTECTED]>
Subject: Adi Shamir's microprocessor bug attack
To: [EMAIL PROTECTED]
Date: Sat, 17 Nov 2007 09:50:31 -0500 (GMT-05:00)


Adi Shamir's note on a microprocessor bug attack on public key cryptography 
featured in the NY Times today:


http://cryptome.org/bug-attack.htm

The NYT report:

http://www.nytimes.com/2007/11/17/technology/17code.html



Can anyone think of a deployed implementation of RSA signatures that 
would be vulnerable to the attack Shamir mentions?  Hashing and message 
blinding would seem to thwart it.


Incidentally, in the 2001 Boneh-DeMillo-Lipton paper they do mention the 
Intel floating point division bug.


-James

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

stickers can deter car theft

[James Muir]

I thought this was an interesting security-related story:

http://www.cbc.ca/canada/nova-scotia/story/2007/05/25/decal-car.html

quoting from the article:


The black-and-yellow sticker, which only costs a loonie, is an
invitation for police to pull over your vehicle if it's on the road
after 1 a.m.

"The problem with car theft is actually bigger than any of us
realize," said Staff Sgt. Peter MacIsaac, with Cape Breton Regional
Police.

Nearly 400 cars were stolen in the Sydney area last year, he said,
and statistics show that most disappear between 1 a.m. and 5 a.m.

MacIsaac said people have been calling the police station to ask
about the Combat Auto Theft (CAT) program, which he says has been a
success in the United States.


Anyone heard of this before?  Is there a reason why a car theft can't 
simply remove or cover up these stickers?


-James

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

Re: Selective disclosure

[James Muir]

I think the first people to consider "i can find Waldo" proofs were
Naor, Naor & Reingold.  You might want to add a reference to their paper 
"Applied Kid Cryptography" in your write-up:


http://www.wisdom.weizmann.ac.il/~naor/PAPERS/waldo_abs.html

-James


Ben Laurie wrote:

I recently wrote a layman's introduction to selective disclosure which
I thought might interest members of this list:
http://www.links.org/files/selective-disclosure.pdf

Cheers,

Ben.

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


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

man in the middle, SSL

[James Muir]

I was reading a hacking blog today and came across this:

http://www.darknet.org.uk/2007/02/odysseus-win32-proxy-telemachus-http-transaction-analysis/ 




Odysseus is a proxy server, which acts as a man-in-the-middle during
an HTTP session. A typical HTTP proxy will relay packets to and from
a client browser and a web server. Odysseus will intercept an HTTP
session’s data in either direction and give the user the ability to
alter the data before transmission.

For example, during a normal HTTP SSL connection a typical proxy will
relay the session between the server and the client and allow the two
end nodes to negotiate SSL. In contrast, when in intercept mode,
Odysseus will pretend to be the server and negotiate two SSL
sessions, one with the client browser and another with the web
server.

As data is transmitted between the two nodes, Odysseus decrypts the
data and gives the user the ability to alter and/or log the data in
clear text before transmission.

You can find more and download Odysseus here:

http://www.bindshell.net/tools/odysseus


It is my understanding that SSL is engineered to resist mitm attacks, so 
I am suspicious of these claims.  I wondered if someone more familiar 
with SSL/TLS could comment.


Isn't in the case that the application doing SSL on the client should 
detect what this proxy server is doing and display a warning to the user?


-James

--
James Muir
http://www.scs.carleton.ca/~jamuir


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

Re: Raw RSA

[James Muir]

Hal Finney wrote:

Alexander Klimov asks:

If an attacker is given access to a raw RSA decryption oracle (the
oracle calculates c^d mod n for any c) is it possible to extract the
key (d)?


This is equivalent to asking whether factoring reduces to RSA inversion.
That is, given access to an RSA inversion oracle, can you factor the
modulus?  (Factoring the modulus is equivalent to finding d.)

Then see "Breaking RSA May Not Be Equivalent to Factoring" by Boneh and
Venkatesan, Eurocrypt 98.  Abstract (with my added emphasis):

"We provide evidence that breaking low-exponent RSA cannot be equivalent
to factoring integers. We show that an algebraic reduction from factoring
to breaking low-exponent RSA can be converted into an efficient factoring
algorithm. THUS, IN EFFECT AN ORACLE FOR BREAKING RSA DOES NOT HELP In
FACTORING INTEGERS. Our result suggests an explanation for the lack of
progress in proving that breaking RSA is equivalent to factoring. We
emphasize that our results do not expose any specific weakness in the
RSA System."

So the answer would appear to be no, an oracle for RSA does not help in
factoring and therefore will not reveal d.

See also http://citeseer.ist.psu.edu/bellare01onemorersainversion.html
"The One-More-RSA-Inversion Problems and the Security of Chaum's Blind
Signature Scheme" by Bellare et al for some discussion of this issue.


Making practical conclusions from the Boneh & Venkatesan result is not a 
very easy task.  See Section 3 of the following


N. Koblitz and A. Menezes
Another Look at Provable Security II
http://www.cacr.math.uwaterloo.ca/~ajmenezes/publications/ps2.pdf

-James





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

Algebraic Attacks on Block Ciphers

[James Muir]

This may interest some list members:

http://eprint.iacr.org/2006/168

Cryptology ePrint Archive: Report 2006/168
How Fast can be Algebraic Attacks on Block Ciphers ?
Nicolas T. Courtois

Abstract. In this paper we give a specification of a new block cipher 
that can be called the Courtois Toy Cipher (CTC). It is quite simple, 
and yet very much like any other known block cipher. If the parameters 
are large enough, it should evidently be secure against all known attack 
methods. However, we are not proposing a new method for encrypting 
sensitive data, but rather a research tool that should allow us (and 
other researchers) to experiment with algebraic attacks on block ciphers 
and obtain interesting results using a PC with reasonable quantity of 
RAM. For this reason the S-box of this cipher has only 3-bits, which is 
quite small. Ciphers with very small S-boxes are believed quite secure, 
for example the Serpent S-box has only 4 bits, and in DES all the 
S-boxes have 4 output bits. The AES S-box is not quite as small but can 
be described (in many ways) by a very small systems of equations with 
only a few monomials (and this fact can also be exploited in algebraic 
cryptanalysis). We believe that results on algebraic cryptanalysis of 
this cipher will have very deep implications for the security of ciphers 
in general.


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

Re: the meaning of linearity, was Re: picking a hash function to be encrypted

[James Muir]

Travis H. wrote:

- Stream ciphers (additive)


This reminds me, when people talk about linearity with regard to a
function, for example CRCs, exactly what sense of the word do they
mean?  I can understand f(x) = ax + b being linear, but how exactly
does XOR get involved, and are there +-linear functions and xor-linear
functions?  Are they disjoint?  etc.


If you have a linear algebra book handy, look up "linear transformation".

Briefly, a function T from a vector space V to another vector space W 
(where V and W are defined over the same field) is called a

linear transformation if it satisfies

i) T(u +_V v) = T(u) +_W T(v)
ii) T(c *_V u) = c *_V T(u)
iii) T(0_V) = 0_W

CRC is a linear transformation because

CRC(u + v) = CRC(u)+CRC(v).

-James

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

Re: webcam encryption beats quasar encryption

[James Muir]

Heyman, Michael wrote:
Internet webcam signals from webcams could emerge as an 
exotic but effective new tool for securing terrestrial 
communications against eavesdropping.

>
> 

Kidding aside, there are some interesting theoretical results about 
ciphers that utilize a plentiful, publicly available source of random 
bits.  See:


http://citeseer.ist.psu.edu/context/238746/0

I think the "Rip Van Winkle cipher" was mentioned in Schneier's Applied 
Cryptography.  Also, I vaguely recall another news story (1999?) that 
reported on an encryption technique that hypothesized a stream of random 
bits generated by an orbiting satellite.


"Quasar encryption" is likely impractical, but there could be more to it 
than you think.  However, I did think "web cam encryption" was funny. :-)


-James

--
James Muir, [EMAIL PROTECTED]
School of Computer Science, Carleton University
http://www.ccsl.carleton.ca/~jamuir

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

Re: Symmetric ciphers as hash functions

[James Muir]

Tom Shrimpton (http://www.cs.pdx.edu/~teshrim/) does research in this 
area (ie. using block ciphers to build hash functions).  See the papers 
on his web site; in particular:


Black-Box Analysis of the Block-Cipher-Based Hash-Function Constructions 
from PGV [pdf] [ps]

John Black, Phillip Rogaway, and Thomas Shrimpton

-James

Arash Partow wrote:

Hi all,

How does one properly use a symmetric cipher as a cryptographic hash
function? I seem to be going around in circles.

Initially I thought you choose some known key and encrypt the data
with the key, using either the encrypted text or the internal state of
the cipher as the hash value, turns out all one needs to do to break
it, is decrypt the hash value with the "known" key and you get a value
which will produce the same hash value.

Reversing the situation (using the data as the key and a known plain-
text) makes a plaintext attack seem like a joy etc..

Are there any papers/books/etc that explain the implementation/use of
symmetric ciphers (particularly AES) as cryptographic hash functions?

btw I know that hash functions and symmetric ciphers share the same
structural heritage (feistel rounds etc...), I just don't seem to be
making the usage link at this point in time... :D

Any help would be very much appreciated.



Kind regards


Arash Partow

Be one who knows what they don't know,
Instead of being one who knows not what they don't know,
Thinking they know everything about all things.
http://www.partow.net


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


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

Re: RSA signatures without padding

[James Muir]

Taral wrote:

On 6/20/05, James Muir <[EMAIL PROTECTED]> wrote:


The attack I am trying to recall is a chosen-message attack and its
efficiency is related to the probability that a random 128-bit integer can
be factorized over a small set of primes (ie. the prob that a uniformily
selected 128-bit integer is "B-smooth" for a small integer B).  Basically,
you pick a message for which you'd like to forge a signature, find a variant
of the message that hashes to a B-smooth 128-bit integer, and then you
construct the forgery after solving a linear system modulo e (the linear
system incorporates the signatures on the chosen messages).



I think you're referring to the Desmedt-Odlyzko selective forgery attack.

See http://www.ipa.go.jp/security/enc/CRYPTREC/fy15/doc/1014_Menezes.sigs.pdf


Yes, that's it.  Thanks for the URL.

-James



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

Re: RSA signatures without padding

[James Muir]

There is an attack against this type of RSA signature scheme, although
cannot remember just now if it requires that the verfication exponent be
small (ie. e=3).

The attack I am trying to recall is a chosen-message attack and its
efficiency is related to the probability that a random 128-bit integer can
be factorized over a small set of primes (ie. the prob that a uniformily
selected 128-bit integer is "B-smooth" for a small integer B).  Basically,
you pick a message for which you'd like to forge a signature, find a variant
of the message that hashes to a B-smooth 128-bit integer, and then you
construct the forgery after solving a linear system modulo e (the linear
system incorporates the signatures on the chosen messages).

I can't think of a reference for this but I will post another message if I
find it.

-James

On Mon, 20 Jun 2005, Florian Weimer wrote:

> I came across an application which uses RSA signatures on plain MD5
> hashes, without padding (the more significant bits are all zero).
> Even worse, the application doesn't check if the padding bits are
> actually zero during signature verification.  The downside is that the
> encryption exponent is fairly large, compared to the modules (27 vs
> 1024 bits). A few hundred signed messages have been published so far.
>
> What do you think?  Are attacks against this application feasible?
> (It should be corrected, of course, but it's not clear if a
> high-priority update is needed.)
>
> -
> The Cryptography Mailing List
> Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
>

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