From: Adam Back <aba@dcs.ex.ac.uk>
Date: Sun, 20 Sep 1998 04:12:34 +0800
To: cypherpunks@cyberpass.net
Subject: Re: CHALLENGE? Toto/signature attack w. unpublished public key
In-Reply-To: <199809200502.HAA08667@replay.com>
Message-ID: <199809200836.JAA28403@server.eternity.org>
MIME-Version: 1.0
Content-Type: text/plain




Anonymous writes:
> > > In addition it has to be that n is the right length based on the "s"
> > > padding.  This limits it to an 8 bit range, in this case 1024-1031
> > > bits.
> > 
> > The constraint I gave was that log(n) = 1024.  Bear in mind that the
> > msbyte of s = 0x08, so we know that n > s, and I think we know that n
> > < 2^1024 also based on the s padding from the signature. So based on
> > this n would be in the range 1020 - 1024 bits, right?
> 
> Actually there is somewhat more flexibility than this.  You made up the
> padding, it didn't come from the file, did it?

I used PGP to make an m to match a 1024 bit n which I presumed from a
1024 bit s; s is from the signature packet from the signed post in
question.  I made the assumption that for a 1024 bit s, the padded
message digest m would be of size 1024 bit also, with it's leading 00
01 FF ... FF etc.  

> You could add perhaps 1 more byte of FF without stretching
> credibility too extremely.  Then n could be 1020 - 1032 bits.  It's
> too bad that s started out so small (assuming the "true" n was 1024
> bits).

I see what you are saying: that if n had been even 1032 bits, it would
still be possible (though relatively unlikely) to result in a s <
1024, which would mean that the m I presumed could have had been a
byte longer.  I think your assumption that PGP would not encode the
leading 0 byte (in the s) is correct, from past PGP code tinkering.
In fact I guess that actually this statement generalises and (with an
even smaller probability) the n could have been 1040 bits, and the s
just happened to come out < 1024 bits, and so on.

I'll see if I can induce this effect by generating a 1025 bit key, and
seeing if any of the signatures come out at 1024 bits:

n =	0x0181291263B847EBEBFDC65E9128DDE9015522B461618F43CDBBF3D707507BA9
	  A71B002F4F852EEC1465710B1641C8816D3E0851C41C2A11E89062E424116A69
	  6E0FB179C7439C6C2F88A214E8D9877658A82982783FA5597262D6CD648111EB
	  A3AB12FC9EB71FB90222624D188E31A3B3333020740860E5F11250D10E2E61F77D
e =	0x11
s =	0x5AA544A471AA79074796D0C85BE01DF44BBED7F14C1189D2D114F8A4E9D4D20E
	  1E67ED9CFA8E20F4D9B84B9C82918F5721D984C7D3A2E2561D399982DFD38873
	  3665745849F83EA14A2D2D586CCB253515E63CF81E2C3927D991E25FAE673DEC
	  E18DB2F6014850CE97F2910393166577F120C4A9512B122F47E05FB117702D6B

So yes, n = 1025 bits, and this particular s is 1023 bits, and this
one is 1025 bits:

s' =	0x012B4B5218E1173DCEF5525C3E9E72BA962371372DA9E9D8D1B469A3BD1060E1
	  5F0ABA0E0BD9B497944FA9AE039F7F006591470857E0CB4FCB460485307A4366
	  54105112BD2E548B6BA9E6B950BC37D39A51ADC169B34935D052DFEEEA9A9FFC
	  BEA4D85BF22D87D66BCB3530EE5316F22A4A4BC4FAB33E592B019E87DE1EAB7336

(most of them work out to be < 1025 bits).

> > > If you make n be a product of a bunch of small primes, so that you
> > > can make signatures with it, then a third party can detect this and
> > > know it is bogus.
> > 
> > He has to factor your n to determine that it is bogus though?  This
> > would imply that he had more compute than you do.  (Not unreasonable
> > threat model mind).
> 
> But didn't YOU have to factor n also?  That's what you showed, originally,
> a large s^e which you factored down to get some small factors and a big
> one.  If you manage to get a prime factorization you can combine factors
> to get your n.  But it won't be any harder for him to factor than it was
> for you.

Yes, you are right.  

Presented with two public keys (n,e), and (n',e') and a signature s,
that even if the attacker manages to factor n but not n' the attacker
can't prove that there isn't another public key (n'',e'') which is the
real key which signed the message.  Ie the reason the attacker is
unable to factor (n',e') may be either because it is a multiple of two
512 bit primes, or because it is a mutliple of primes of special form
I quoted a post describing in the other post, and he doesn't have
enough compute to recover it.  With the quoted algorithm from Maurer,
the attacker needs more compute to show that the key has a special
form than you do to create the key.

Adam