Cryptography-Digest Digest #855, Volume #10 Thu, 6 Jan 00 13:13:01 EST
Contents:
Re: is signing a signature with RSA risky? (Anton Stiglic)
Re: is signing a signature with RSA risky? (Anton Stiglic)
Re: How about this for a "randomly" generated bitstream? (Tim Tyler)
Re: Unsafe Advice in Cryptonomicon (John Savard)
Re: Can CRC16 become 0? (John Savard)
Re: Unsafe Advice in Cryptonomicon ("anonymous intentions")
Re: Miller Rabin alg--which is the right one? (Tom St Denis)
Re: Simon Sigh Enigm (Tim Tyler)
Re: simple block ciphers (Anton Stiglic)
Re: Unsafe Advice in Cryptonomicon (Albert P. Belle Isle)
Re: How about this for a "randomly" generated bitstream? (Scott Nelson)
----------------------------------------------------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: is signing a signature with RSA risky?
Date: Thu, 06 Jan 2000 11:59:38 -0500
==============BF7D4B0713F33805F5C344B6
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
What? The trick is not just with RSA, it can also be done with a variation
on ElGamal (with a corrupt prime for example), and who knows what else.
The principal of Signing before encrypting doesn't come from Mr. Shneier,
it in fact comes from Abadi and Needham "Prudent Engineering Practice
for Cryptographic Protocols" and re-stated (and re-affirmed) in the article
by Anderson and Needhman "Robustness principles for public key protocols".
About your argument: firstly, the signature keys and encryption keys are
should be totaly independent (this is obvisous, since the private parts
belong
to two different entities). So the failling of a signature verification
doesn't tell
you anything about the encrypted message or the key used for encryption.
Secondly, you have to decrypt first, and then verify the signature of the
message
(in a private fashion, of cours). Publicaly verifying a message doesn't
mean
you need to publicaly diffuse the message, it just means that you get a
public
key to verify it privately. If you have to show it to some on (in order to
prove
something), you have to show the cleartext (showing just the ciphertext won't
proove anything). So I don't see any valid arguments....
Anton
Tim Tyler wrote:
> Pascal Scheffers <[EMAIL PROTECTED]> wrote:
>
> : With RSA, there is the risk that if you encrypt before signing the
> : other can fake a message. This is described on p473 of Applied
> : Cryptography 2nd.Ed.
>
> BS says there that: "It makes sense to sign a message before encrypting
> it".
>
> Any users who follow this advice should be aware that if the signature may
> be publicly validated, this can provide a concrete halting criterion -
> which allows keys to be automatically rejected on every signed message
> sent.
>
> I believe you should normally sign outside at least one layer of strong
> encryption, because of this (with different key bits being used on "either
> side" of the signature).
>
> This way, if an attack using the signature succeeds, at least the
> message itself is not automatically compromised.
>
> If you don't do this you should be aware there may be a security price
> to authenticating your message.
>
> I don't mean to advocate falling into the path of the RSA
> encrypt-before-signing attack, of course.
> --
> __________
> |im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
>
> How did a fool and his money get together in the first place?
--
___________________________________________
Anton Stiglic
Jr. developer & specialist in cryptology.
Zero-Knowledge Systems Inc.
___________________________________________
==============BF7D4B0713F33805F5C344B6
Content-Type: text/html; charset=us-ascii
Content-Transfer-Encoding: 7bit
<!doctype html public "-//w3c//dtd html 4.0 transitional//en">
<html>
<br>What? The trick is not just with RSA, it can also be done
with a variation
<br>on ElGamal (with a corrupt prime for example), and who knows what else.
<br>The principal of Signing before encrypting doesn't come from Mr. Shneier,
<br>it in fact comes from Abadi and Needham "Prudent Engineering Practice
<br>for Cryptographic Protocols" and re-stated (and re-affirmed) in the
article
<br>by Anderson and Needhman "Robustness principles for public key protocols".
<br>About your argument: firstly, the signature keys and encryption
keys are
<br>should be totaly independent (this is obvisous, since the private parts
belong
<br>to two different entities). So the failling of a signature verification
doesn't tell
<br>you anything about the encrypted message or the key used for encryption.
<br>Secondly, you have to decrypt first, and then verify the signature
of the message
<br>(in a private fashion, of cours). Publicaly verifying a
message doesn't mean
<br>you need to publicaly diffuse the message, it just means that you get
a public
<br>key to verify it privately. If you have to show it to some on (in order
to prove
<br>something), you have to show the cleartext (showing just the ciphertext
won't
<br>proove anything). So I don't see any valid arguments....
<br>
<br>
<p>Anton
<br>
<br>
<p>Tim Tyler wrote:
<blockquote TYPE=CITE>Pascal Scheffers <[EMAIL PROTECTED]> wrote:
<p>: With RSA, there is the risk that if you encrypt before signing the
<br>: other can fake a message. This is described on p473 of Applied
<br>: Cryptography 2nd.Ed.
<p>BS says there that: "It makes sense to sign a message before encrypting
<br>it".
<p>Any users who follow this advice should be aware that if the signature
may
<br>be publicly validated, this can provide a concrete halting criterion
-
<br>which allows keys to be automatically rejected on every signed message
<br>sent.
<p>I believe you should normally sign outside at least one layer of strong
<br>encryption, because of this (with different key bits being used on
"either
<br>side" of the signature).
<p>This way, if an attack using the signature succeeds, at least the
<br>message itself is not automatically compromised.
<p>If you don't do this you should be aware there may be a security price
<br>to authenticating your message.
<p>I don't mean to advocate falling into the path of the RSA
<br>encrypt-before-signing attack, of course.
<br>--
<br>__________
<br> |im |yler The Mandala Centre <a
href="http://www.mandala.co.uk/">http://www.mandala.co.uk/</a>
[EMAIL PROTECTED]
<p>How did a fool and his money get together in the first place?</blockquote>
<pre>--
___________________________________________
Anton Stiglic <[EMAIL PROTECTED]>
Jr. developer & specialist in cryptology.
Zero-Knowledge Systems Inc.
___________________________________________</pre>
</html>
==============BF7D4B0713F33805F5C344B6==
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: is signing a signature with RSA risky?
Date: Thu, 06 Jan 2000 12:09:52 -0500
Pascal Scheffers wrote:
> Okay, so signing a signature basically means sign-after-encryption,
> with the difference that you are not encrypting with the public
> exponent, but the private.
I don't understand what you mean. You sign a message (not a
signature). And the way to avoid an attack is to sign first, then
encrypt. The keys for the signature scheme are independant
from the keys of the encryption scheme, to understand the
attack on sign after encrypte, you can use any signature scheme.
>
> So when Alice signs Bobs signature, you get
>
> (m^s_b mod n_b)^s_a mod n_a
>
You don't sign anybody's signature. The attack happens whey
you sign an encrypted message, example:
Sign(Alice, (m^e_b mod n_b))
where
e_b is Bob's public encryption key,
d_b would be Bob's private decryption key,
n_b would be Bob's modulus for the RSA scheme
And Sign(Alice, y) would be a function that outputs
Alice's signature on the message y.
It happens to be that RSA has a signature scheme, so using
s_a: Alice private signature key,
v_a: public verification key for Alice's signatures.
n_a: the modulus for the signature key,
we get:
(m^e_b mod n_b)^s_a mod n_a
The right thing to do (to prevent the attack) is sign before you
encrypt:
(Sign(Alice, m))^e_b mod n_b
Using RSA signature and encryption, it would look like
(m^s_a mod n_a)^e_b mod n_b
Bob doen't know the factorisation of n_b
In this last case, there is nothing Bob could do to cheat...
Anton
>
>
> Bob still knows his factorisation, so now it's even easier - all he
> has to do is find another s_b, and he doesn't even have to tell the
> world he did it, because nothing changes for the outside world.
>
> Or is this a hard problem? I think it should be, but... I am
> definitely not a mathematician.
>
> Rgds.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: How about this for a "randomly" generated bitstream?
Reply-To: [EMAIL PROTECTED]
Date: Thu, 6 Jan 2000 17:04:25 GMT
Scott Nelson <[EMAIL PROTECTED]> wrote:
: On 05 Jan 2000 21:35:17 EST, [EMAIL PROTECTED] (Guy Macon) wrote:
:>I know hardware, and I am very confident that I can achieve a 99.X%
:>[99.9? 99.99? 99.999?], and that I will never be able to prove 100%.
:>Folks who know crypto better than I do tell me that they can not prove
:>that 99.X% is good enough for certain crypto uses.
:
: 99.999999999999% is pretty easy to achieve if you're willing
: to spend some time collecting and hashing the data.
Such figures appear fantastic to me - at least when cryptographic
application is being discussed.
If the oppenent can get any access to the stream it is immediately
non-random, since given "n" bits of the stream, the opponent can predict
the net and previous bits.
Similarly you have to guard against the opponent being able to influence
the generated stream, since if he can gain access he can /easily/
substitute a pseudo-random stream with a very low entropy content that
nevertheless passes all the best tests for randomness available.
Any figure put on the entropy content of a stream intended for
cryptographic purposes should figure this sort of thing into the
equation somewhere, IMO - at the very least as a measure of confidence
in the entropy figure.
Can you be 99.999999999999% confident that your opponent has not
surreptitiously substituted his own PRNG for your own system of hashes?
If not how can you claim with any certainty that you have an entropy
content of 0.99999999999999? Is it not possible that you're hypnotised,
in the presence of a magician, or that your assistant is an enemy agent?
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
To be born rich is an accident - to die rich is a miracle.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Unsafe Advice in Cryptonomicon
Date: Thu, 06 Jan 2000 10:07:12 GMT
[EMAIL PROTECTED] (Steve K) wrote, in part:
>And one more technical quibble from Cryptonomicon, about a computer
>room with an electromagnet in the door frame, that wipes any media
>being carried in or out:
Better leave your wallet outside...
John Savard (jsavard<at>ecn<dot>ab<dot>ca)
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Can CRC16 become 0?
Date: Thu, 06 Jan 2000 10:10:14 GMT
[EMAIL PROTECTED] (Arjan) wrote, in part:
>If this is the
>only case where the CRC16 becomes zero, I could use it to check if the
>memory device is empty.
No, it definitely isn't. Given random bits in your memory device, all
65536 possible CRC-16 checksums are equally probable.
Of course, while you're calculating the CRC-16, you're scanning
through every byte in the memory anyways, so a check of every byte in
the device won't take longer than that had taken.
John Savard (jsavard<at>ecn<dot>ab<dot>ca)
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: "anonymous intentions" <[EMAIL PROTECTED]>
Subject: Re: Unsafe Advice in Cryptonomicon
Date: Thu, 6 Jan 2000 09:14:02 -0600
I am not sure if that was intended to be comical, but may I mention that
it is possible to create a neutral magnetic field where the polarities are
neither favored in any biased direction. This being the case, it then may
suggest that no one would really "feel" anything physical such as in pull.
But if someone were to use a magnetic compass it would probably be spinning
around crazily and anyone with a brain would figure to take that down first
before just slipping anything out. I am sure watches, maybe pacemakers,
walkman's and anything sensitive to emp/herf would also fizz to where it
would be noticable. This can of course then be camoflauged by implanting a
switch (which I don't think was placed in the door paneling) that when
walked within a perimeter that may be at 100% flux effective, active the
field, and only at that time and no other.. a good algorithm to run would
be..
if ( body.mass.a[beforedoor] > body.mass.a[afterdoor] ) then MagneticField
else
NoMagneticField
Which would logically reason that a exiting is heavier than when a entered
probably carrying the computer.
This would be thrown out if a tossed the computer to b on the otherside of
the door.
So then it would be better to install a false isa/pci card that is self
powered (such as some hardware randgens are) and have it run as a proximity
beacon so that if Beacon.Distance nears MagneticProximity to FluxThreshold
it would zap the machine to no one being wiser. Which would also be the best
solution especially since triggering can be installed so that if the case is
opened or tampered the MagneticFlux would hit EmergencyTerroristMode and fry
anything in the room (which would probably cause some brain problems and
passing out)...
With security in mind and paranoia set, anyone can make something
impenetrable, you just then have to worry about someone with more security,
paranoia to think like you, then think aroud you..
Life is grand..
feel free to email me [EMAIL PROTECTED] public key is posted.
spam is kill filtered.
I loved that book Cryptonomicon as well as Snowcrash... I must be a
stephenson fan. I hate fans.
"Steve K" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> On Thu, 06 Jan 2000 06:27:57 GMT, [EMAIL PROTECTED] (Steve K) wrote:
>
> And one more technical quibble from Cryptonomicon, about a computer
> room with an electromagnet in the door frame, that wipes any media
> being carried in or out: OK fine, if the field is strong enough to
> wipe media at the distances involved (typically 1-1/2 feet or so) and
> through the ferrous materials in the housings & etc. And OK fine, if
> the people carrying the stuff out through this field do not notice
> that every piece of ferrous metal that comes close to the frame gets
> yanked out of their hands.
>
> Oops. Heh heh. OK so the first thing they tried to carry out was the
> one thing that really did need wiped.
>
> Clank! "What the-- oh sh*t!"
>
> Plot line saved. Ta daa.
>
>
> Steve K
>
> ---Continuing freedom of speech brought to you by---
> http://www.eff.org/ http://www.epic.org/
> http://www.cdt.org/
>
> PGP key 0x5D016218
> All others have been revoked.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Miller Rabin alg--which is the right one?
Date: Thu, 06 Jan 2000 17:07:36 GMT
In article <852at1$t09$[EMAIL PROTECTED]>,
Bob Silverman <[EMAIL PROTECTED]> wrote:
> In article <sq1d4.853$15.4442@news>,
> "Miryadi" <[EMAIL PROTECTED]> wrote:
> > Hello, all
> >
> > Cormen's "Introduction To Algorithm" page 843 mention that:
> > for any odd integer n>2 and positif integer s, the probability that
> > Miller_Rabin (n,s) error is at most 2^-s, but
> >
> > Menezes' "Handbook of Cryptography" page 140 mention that:
> > for any composite integer n, the probability that Miller_Rabin(n,t)
> > declares n to be prime is less than (1/4)^t.
> >
> > Which is the right one?
>
> NEITHER. But Meneze's is closer to the truth. M-R(n,t) < 1/4^t is
> true only for large enough n. But this bound is very WEAK. The truth
> is that the probability is MUCH smaller.
>
> See:
>
> Kim & Pomerance
> "The Probability that a random probable prime is composite"
> Math. Comp. 53 (1989)
>
While we are on the subject... What is the probability that a prime 'n'
cheat a Fermat Little Theorem test when using 's' prime witnesses.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
Crossposted-To: fido7.crypt,fr.misc.cryptologie
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Simon Sigh Enigm
Reply-To: [EMAIL PROTECTED]
Date: Thu, 6 Jan 2000 17:10:47 GMT
James Taylor <[EMAIL PROTECTED]> wrote:
: My own version of the book has encrypted the texts at the back in more than
: one language: English, Latin and French. [...]
Hmm. Do these versions of the book cost extra? ;-)
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
Jesus saves... Vishnu invests...
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: simple block ciphers
Date: Thu, 06 Jan 2000 12:26:44 -0500
Tom St Denis wrote:
> In article <[EMAIL PROTECTED]>,
> Anton Stiglic <[EMAIL PROTECTED]> wrote:
> > Hi Tom,
> >
> > Given enough ciphertext, you can pretty much guess what p is
> > (since all the ciphertexts will be between the values 1 and p-1).
> > If you use it as a block cipher, you'll get quiet a few ciphertexts.
> > So for reasonable use, you can consider p to be known.
>
> A large num of C though... since we get
>
> a = 2^72/ln 2^72 = ~2^66.35
> b = 2^64/ln 2^64 = ~2^58.52
>
> c = a - b = ~2^66.34
>
> So in the case where 8 byte blocks are encrypted with a 72-bit prime
> modulus there are c possible prime moduli. Obviously just checking
> them all is not a happening thing.
>
You are right, you would need a more intelligent attack to get p. I
beleive
that one exists do, but I don't rember what it is or where you can find
it
(so can't give you much help there).
>
> > Now, a problem beleived to be hard is given a prime p, a generator
> > g and an element y, find x such that g^x = y mod p (this is the DH
> > problem). The basis (the generator g) is fixed! In your case, the
> > base is not fixed, this changes the problem (the problem is not
> > equivalent to the DH problem) I can't think of any usefull type of
> > attack right now do.
> >
> > Now, some notes on the algo. Firstly, why do you choose e to be
> > prime?
> > Secondly, if you want d to exist, you must have gcd(e, p-1) = 1
> > (unless you work in some sub group of order q, and in that case
> > q has to be big enough for security reasons).
> > Thirdly, if in fact you realy want e to be prime, then you realy
> restrict
> >
> > the possible amount of e's, since you have to have gcd(e,p-1) =1
> > and e is prime, e would have to be a factor of p-1. (If you know the
> > factorization of p-1, it's probably an easy search...).
>
> Thanks for pointing that out. I actually realized why it didn't work
> [at first I was using random e values]. When I posted it, that was
> just off the top of my head. I am teaching myself number theory [with
> the help of Michael Froberger]. In the current source code I am
> playing with I do the GCD instead of a prime.
As Mr. Molnar pointed out do, my last argument was wrong.
If e has to be prime, to have gcd(e, p-1) = 1, e should not be
a factor of p-1, so we don't get much info with this.
But yes, gcd(e, p-1) must be 1 so that the inverse of e can exist
(when you work in a group mod p, where p is prime, you can think
of your exponents working in a group p-1 (this is because the order
of the group is p-1. In a genral case, a group mod n has order
phi(n), where phi is the euler fonction).
For an element x of a group mod n to have an inverse, you must
have gcd(x,n) = 1. Note that if n is prime, all x in the group mod n
will be such that gcd(x, n) = 1, this is why all elements in a group
mod p (p prime) have inverses...)..
Anton
------------------------------
From: Albert P. Belle Isle <[EMAIL PROTECTED]>
Subject: Re: Unsafe Advice in Cryptonomicon
Date: Thu, 06 Jan 2000 12:26:25 -0500
Reply-To: [EMAIL PROTECTED]
On Thu, 06 Jan 2000 16:29:31 GMT, [EMAIL PROTECTED] (Steve K) wrote:
>On Thu, 06 Jan 2000 06:27:57 GMT, [EMAIL PROTECTED] (Steve K) wrote:
>
>And one more technical quibble from Cryptonomicon, about a computer
>room with an electromagnet in the door frame, that wipes any media
>being carried in or out: OK fine, if the field is strong enough to
>wipe media at the distances involved (typically 1-1/2 feet or so) and
>through the ferrous materials in the housings & etc. And OK fine, if
>the people carrying the stuff out through this field do not notice
>that every piece of ferrous metal that comes close to the frame gets
>yanked out of their hands.
>
>Oops. Heh heh. OK so the first thing they tried to carry out was the
>one thing that really did need wiped.
>
>Clank! "What the-- oh sh*t!"
>
>Plot line saved. Ta daa.
>
>
>Steve K
>
Steve:
Great plot-save.
However the kind of magnetic field used to purge magnetic data
remanence is an alternating magnetic field - as in Type II
degaussers.
Perhaps your plot-save could involve (extremely) rapid "Clank"-ing
back-and-forth to alternate sides of the door-frame? ;-)
Albert P. BELLE ISLE
Cerberus Systems, Inc.
================================================
ENCRYPTION SOFTWARE with
Forensic Software Countermeasures
http://www.CerberusSystems.com
================================================
------------------------------
From: [EMAIL PROTECTED] (Scott Nelson)
Subject: Re: How about this for a "randomly" generated bitstream?
Reply-To: [EMAIL PROTECTED]
Date: Thu, 06 Jan 2000 17:51:02 GMT
On Thu, 6 Jan 2000 17:04:25 GMT, Tim Tyler <[EMAIL PROTECTED]> wrote:
>Scott Nelson <[EMAIL PROTECTED]> wrote:
>: On 05 Jan 2000 21:35:17 EST, [EMAIL PROTECTED] (Guy Macon) wrote:
>
>:>I know hardware, and I am very confident that I can achieve a 99.X%
>:>[99.9? 99.99? 99.999?], and that I will never be able to prove 100%.
>:>Folks who know crypto better than I do tell me that they can not prove
>:>that 99.X% is good enough for certain crypto uses.
>:
>: 99.999999999999% is pretty easy to achieve if you're willing
>: to spend some time collecting and hashing the data.
>
>Such figures appear fantastic to me - at least when cryptographic
>application is being discussed.
>
>If the oppenent can get any access to the stream it is immediately
>non-random, since given "n" bits of the stream, the opponent can predict
>the net and previous bits.
>
>Similarly you have to guard against the opponent being able to influence
>the generated stream, since if he can gain access he can /easily/
>substitute a pseudo-random stream with a very low entropy content that
>nevertheless passes all the best tests for randomness available.
>
>Any figure put on the entropy content of a stream intended for
>cryptographic purposes should figure this sort of thing into the
>equation somewhere, IMO - at the very least as a measure of confidence
>in the entropy figure.
>
>Can you be 99.999999999999% confident that your opponent has not
>surreptitiously substituted his own PRNG for your own system of hashes?
>
>If not how can you claim with any certainty that you have an entropy
>content of 0.99999999999999? Is it not possible that you're hypnotised,
>in the presence of a magician, or that your assistant is an enemy agent?
>
If your definition of randomness includes the concept of
security of the randomness, then I agree that it's no longer
easy to achieve that level of certainty. I think it's still
possible, but it's certainly not something that you can do
in your garage.
I was referring to the level of confidence one can have
that the system is producing unguessable bits,
_assuming that everything is working properly_.
It would probably be more useful to say;
It's easy to generate randomness with less error and
more confidence than you can reasonably have for the
storage system that keeps it.
Scott Nelson <[EMAIL PROTECTED]>
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
