Cryptography-Digest Digest #744, Volume #11 Tue, 9 May 00 17:13:01 EDT
Contents:
Re: RSA-primes, smoothness (Roger Schlafly)
Re: zeroknowledge.com and freedom.net - Snake oil? ("Dr. Yongge Wang")
Re: UK issue; How to determine if a file contains encrypted data? (Roger Schlafly)
Re: F function. (Tom St Denis)
Re: RSA (Tom St Denis)
Re: More on Pi and randomness (Bob Silverman)
Re: Q: Searching for authentication protocols (Thomas Wu)
Re: RSA-primes, smoothness (DJohn37050)
The RSA patent and my software (Tom St Denis)
Re: RSA-primes, smoothness (Roger Schlafly)
Re: quantum crypto breakthru? (Bill Unruh)
Re: More on Pi and randomness (Mok-Kong Shen)
Re: quantum crypto breakthru? (Roger Schlafly)
Re: More on Pi and randomness (Roger Schlafly)
Re: RSA (Bill Unruh)
Re: The RSA patent and my software (Tom St Denis)
Re: F function. (Mark Wooding)
Re: F function. (Mark Wooding)
----------------------------------------------------------------------------
From: Roger Schlafly <[EMAIL PROTECTED]>
Subject: Re: RSA-primes, smoothness
Date: Tue, 09 May 2000 12:17:54 -0700
DJohn37050 wrote:
> No, they decided that the cost was nominal, and worth the disambiguation. What
> do you do if someone presents a RSA key where p-1 HAS all small factors? Go
> before a judge and let HIM/HER decide? Or perhaps worse, a jury?
A jury might do better than the ANSI committee. Apparently you are
worried that someone will deliberately create a defective RSA key
so he can disavow signatures.
I say it is snake oil because it gives an illusion of security
when there actually is none. If someone wants to make an RSA key
that he will disavow later, there are other ways:
1. Reuse a key that has already been compromised.
2. Use a badly defective random number generator.
3. Use a modulus that happens to factor easily for some other
reason (than p-1 being a product of small factors).
> Given these possibilities, the answer for banks was to disallow this
> possibility. If anyone comes and presents such an RSA key, it does not meet
> the standard.
What if someone uses one of the sample keys in the ANSI doc.
Will that meet the standard? What would you want to do with
someone who uses one of those keys? Let a jury decide?
------------------------------
From: "Dr. Yongge Wang" <[EMAIL PROTECTED]>
Subject: Re: zeroknowledge.com and freedom.net - Snake oil?
Date: 9 May 2000 19:21:53 GMT
Guy Macon <[EMAIL PROTECTED]> wrote:
Seems the same thing as the Crowds by ATT research lab.
Not read the details yet. The problem is that if one guy
has access to all these freenet proxies, then he can
trace the log file and trace back u.. u will not be anonymous
then .
: I am interested in a Canadian company called Zero-Knowledge Systems
: at [ http://www.zeroknowledge.com/ ], [ http://www.zks.net ] and
: [ http://www.freedom.net/ ]. They claim a cryptographically secure
: method of providing anonymity. Does anyone know whether this is
: snake oil? The technical and crypto details are at
: [ http://www.freedom.net/info/freedompapers/index.html ].
: Quotes from [ http://www.zeroknowledge.com/media/stefanbrands_bio.asp ]
: "Dr. Stefan Brands is an internationally recognized cryptographer"
: "Dr. Brands is the owner of eight international patents on electronic
: cash and digital certificates. In February of 2000 he joins
: Zero-Knowledge Systems, a developer of Internet privacy and
: identity-management systems, as Distinguished Scientist to further
: develop and implement electronic cash and private credential systems
: for the online and physical worlds"
: Quotes from [ http://www.zeroknowledge.com/media/freedom-sb.asp ]
--
======================================================.
Yongge Wang |
Center for Applied Cryptographic Research |
University of Waterloo |
Waterloo, Ontario, N2L 3G1 |
Canada |
Phone:(519)8884567 x 5295 |
[EMAIL PROTECTED] |
http://cacr.math.uwaterloo.ca/~ygwang |
======================================================'
------------------------------
From: Roger Schlafly <[EMAIL PROTECTED]>
Subject: Re: UK issue; How to determine if a file contains encrypted data?
Date: Tue, 09 May 2000 12:25:22 -0700
JoeC wrote:
> If I was to hide a PGP or similar encrypted message within the least
> significant bits of a JPEG, and the normal PGP/whatever headers had been
> removed, is there any way to determine if that file contains encrypted data?
> Maybe through some sort of statistical or other determination of
> non-randomness?
Search for "steganography" and you'll find info on hiding data.
> I'm not suggesting this is original thought, since I know its not, but I was
> wondering what the situation would be in regard to the pending UK
> legislation on encryption. Because if it can't even be proven that a file
> contains hidden data then this makes a complete mockery of the requirement
> to reveal keys, since the defence would be 'this is an entirely innocent
> picture, there is no key, and you cant even show any encrypted data'.
Finding a clever way to evade the law does not make a complete
mockery of it. There are clever ways of evading a lot of laws.
But those who get caught can still goto jail.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: F function.
Date: Tue, 09 May 2000 19:29:07 GMT
[EMAIL PROTECTED] wrote:
>
> I am intrested in this bit:
>
> > Your comments on finding the inverse of the function
> > seem to contain some confusions. First, it is not
> > bijective, so there isn't an inverse
>
> Answer: That's what i was proving, i assumed that the calculated powers
> being equal was a direct sign of non-invertibility.
45^x mod 257 has an inverse,
44^x mod 257 does not.
> >Second you
> > seem to be mis-applying the Euclidean algorithm.
> > Also, the integers mod 256 do not form a finite field.
>
> This really intrests me, What is a finite field then?
> I thought the Extended Euclidean algorithm is for solving problems of
> the nature:
If the number is relatively prime with the modulus. In this case you
can't say that always, and your modulus has to be prime for it to work.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: RSA
Date: Tue, 09 May 2000 19:36:15 GMT
[EMAIL PROTECTED] wrote:
> Hold on, if it the output, for some base raised to some exponent, is
> bias for the modulo of a product of two primes, couldn't this be used
> to recover the plain-text?
Take 2^x mod 13, the order of this group is 12, where as 3^x mod 13 has
order 6. This means any element of 3^x mod 13, is twice as likely to be
the output then in 2^x mod 13.
However in RSA we are talking about huge numbers, so the bias is a)
hardly noticeable at all, b) not easy to exploit.
To exploit that you would have to...
S = M^d mod n
Now given the order of M mod n, you can reduce this to
M^(d mod n') mod n
How you exploit this is difficult...
For example if I give C=-1, I can reduce e mod 2 to get d' = d mod 2,
and find the the lsb of the RSA private key. For example
1 = -1^d mod n
1 = -1^0 mod n
Which means the private key is even.
The smaller the subgroup the better, you can also take discrete logs in
that field too. If you have
d' = d mod n'
You are essentially trying to solve for
S = M^d' mod n
etc...
Tom
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: More on Pi and randomness
Date: Tue, 09 May 2000 19:25:27 GMT
In article <[EMAIL PROTECTED]>,
JCA <[EMAIL PROTECTED]> wrote:
>
<snip>
> To
> put it in a different way: I wouldn't use the decimal expansions of
> these two numbers
> for cryptographic purposes, but I would certainly be tempted to do so
> with Pi,
> provided I can choose where to start in the expansion.
>
> Comments are welcome.
Comments? OK, but you won't like it.
Your proposal is cryptographically very weak.
To see this is trivial. You propose a using a specific random string of
digits. This is no better than using a pseudo-rng, but in your case the
seed consists of the pair (pi, starting point). This is not a lot
of entropy. In fact, it is very little.
Using *named* transcendental constants is not cryptographically
useful. There are not enough of them and whichever you select is easily
guessed.
--
Bob Silverman
"You can lead a horse's ass to knowledge, but you can't make him think"
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Thomas Wu <[EMAIL PROTECTED]>
Crossposted-To: comp.security.misc
Subject: Re: Q: Searching for authentication protocols
Date: 09 May 2000 12:43:34 -0700
Tomīs Perlines Hormann <[EMAIL PROTECTED]> writes:
> Thanks a lot for these hints, but I guess strong password authentication
> may not be enough as we need to exchange symmetric keys in order to have
> a secure communciation channel during the authentication (handshake)
> protocol.
Strong password authentication protocols like SRP and SPEKE also exchange
a symmetric session key as a byproduct of successful authentication.
You can use this key to provide session integrity and confidentiality.
--
Tom Wu * finger -l [EMAIL PROTECTED] for PGP key *
E-mail: [EMAIL PROTECTED] "Those who would give up their freedoms in
Phone: (650) 723-1565 exchange for security deserve neither."
http://www-cs-students.stanford.edu/~tjw/ http://srp.stanford.edu/srp/
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Subject: Re: RSA-primes, smoothness
Date: 09 May 2000 19:58:33 GMT
>I say it is snake oil because it gives an illusion of security
>when there actually is none. If someone wants to make an RSA key
>that he will disavow later, there are other ways:
>
>1. Reuse a key that has already been compromised.
* This can be addressed by not allowing certification of a compromised key.
>2. Use a badly defective random number generator.
* This is difficult to detect. If an adversary has extra knowledge, everything
can look fine, except he can crack it. FIPS 140-1 tests are one way to try to
address an inadvertant bad RNG.
>3. Use a modulus that happens to factor easily for some other
>reason (than p-1 being a product of small factors).
* Regarding EC factoring, it was thought that "guessing" the right curves to
factor p would not be plausible, but that having p-1 contain all small factors
might be plausible, so it was excluded. That is, the p-1 and p+1 attacks work
on only a small fraction of keys, so it is easy to exclude that small fraction.
>
>> Given these possibilities, the answer for banks was to disallow this
>> possibility. If anyone comes and presents such an RSA key, it does not
>meet
>> the standard.
>
>What if someone uses one of the sample keys in the ANSI doc.
>Will that meet the standard? What would you want to do with
>someone who uses one of those keys? Let a jury decide?
* No, these should be excluded.
Don Johnson
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: The RSA patent and my software
Date: Tue, 09 May 2000 19:59:50 GMT
You guys seem to argue a bunch about it.
I have chosen the mature way todo things is to not use RSA or any RSA
ciphers until allowed.
So basically I will not use RSA here or there until Sept 21st.
Tom
--
Want your academic website listed on a free websearch engine? Then
please check out http://tomstdenis.n3.net/search.html, it's entirely
free
and there are no advertisements.
------------------------------
From: Roger Schlafly <[EMAIL PROTECTED]>
Subject: Re: RSA-primes, smoothness
Date: Tue, 09 May 2000 13:15:21 -0700
DJohn37050 wrote:
> >I say it is snake oil because it gives an illusion of security
> >when there actually is none. If someone wants to make an RSA key
> >that he will disavow later, there are other ways:
> >
> >1. Reuse a key that has already been compromised.
> * This can be addressed by not allowing certification of a compromised key.
What, the bankers have a database of all compromised keys? And the
cert authorities check it on every request?
> >2. Use a badly defective random number generator.
> * This is difficult to detect. If an adversary has extra knowledge, everything
> can look fine, except he can crack it. FIPS 140-1 tests are one way to try to
> address an inadvertant bad RNG.
That might help avoid an "inadvertant bad RNG", but does nothing to
stop your hypothetical case of someone who wants to make a bad key.
Using a bad RNG is much simpler and easier than fooling around with
p-1 factors anyway.
> >3. Use a modulus that happens to factor easily for some other
> >reason (than p-1 being a product of small factors).
> * Regarding EC factoring, it was thought that "guessing" the right curves to
> factor p would not be plausible, but that having p-1 contain all small factors
> might be plausible, so it was excluded. That is, the p-1 and p+1 attacks work
> on only a small fraction of keys, so it is easy to exclude that small fraction.
It sounds like you already have an opinion about what a judge and
jury will believe.
> >> Given these possibilities, the answer for banks was to disallow this
> >> possibility. If anyone comes and presents such an RSA key, it does not
> >meet
> >> the standard.
> >
> >What if someone uses one of the sample keys in the ANSI doc.
> >Will that meet the standard? What would you want to do with
> >someone who uses one of those keys? Let a jury decide?
>
> * No, these should be excluded.
You mean the standard ought to prohibit these? Even if it does, what
if NIST or someone else publishes another list of samples?
What do you want to do, amend the standard or let a jury decide?
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: quantum crypto breakthru?
Date: 9 May 2000 20:41:49 GMT
In <[EMAIL PROTECTED]> Francois Grieu
<[EMAIL PROTECTED]> writes:
>How, if Eve negociates a key KA with Alice, another KB with Bob,
>deciphers the message sent by Alice using KA, and reciphers it with KB
>for Bob ? My hypothecial active eavesdropping setup in unchanged,
>provided the key generation and en/de/cipherement is built into the
That is why Alice and Bob must share some secret before hand so that
they can authenticate the interchange. The thing about QC is that that
initial secret can be amplified -- eg 100 bits of secret can be made
into 10000000000000000 bits of shared secret.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: More on Pi and randomness
Date: Tue, 09 May 2000 22:53:28 +0200
Bob Silverman wrote:
> JCA <[EMAIL PROTECTED]> wrote:
> > To
> > put it in a different way: I wouldn't use the decimal expansions of
> > these two numbers
> > for cryptographic purposes, but I would certainly be tempted to do so
> > with Pi,
> > provided I can choose where to start in the expansion.
>
> Your proposal is cryptographically very weak.
>
> To see this is trivial. You propose a using a specific random string of
> digits. This is no better than using a pseudo-rng, but in your case the
> seed consists of the pair (pi, starting point). This is not a lot
> of entropy. In fact, it is very little.
Question: If one gets a number of disjoint segments of Pi, have these
as input to good a block cipher and xor the different output sequences,
would the result be practically useful? Thanks.
M. K. Shen
------------------------------
From: Roger Schlafly <[EMAIL PROTECTED]>
Subject: Re: quantum crypto breakthru?
Date: Tue, 09 May 2000 13:50:10 -0700
Bill Unruh wrote:
> The thing about QC is that that
> initial secret can be amplified -- eg 100 bits of secret can be made
> into 10000000000000000 bits of shared secret.
Nothing unusual about that. Conventional cryptosystems claim
to do that also. They might use a 100 bit cipher key to
encrypt (and share) gigabytes of data.
------------------------------
From: Roger Schlafly <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: More on Pi and randomness
Date: Tue, 09 May 2000 13:52:52 -0700
Mok-Kong Shen wrote:
> Question: If one gets a number of disjoint segments of Pi, have these
> as input to good a block cipher and xor the different output sequences,
> would the result be practically useful? Thanks.
Better yet, take a chunk of the binary expansion of Pi, and
rearrange all the 0s and 1s randomly! <g>
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: RSA
Date: 9 May 2000 20:58:44 GMT
In <8f9hkt$i8e$[EMAIL PROTECTED]> [EMAIL PROTECTED] writes:
]In article <[EMAIL PROTECTED]>,
] Tom St Denis <[EMAIL PROTECTED]> wrote:
]> > Sorry, i think you missed my question, through my badd phrasing.
]> >
]> > 1.) Does RSA produce an evenly-distrubuted range of output values,
](that
]> > looks random, but of course isn't.)?
Yes.
]>
]> Not really, it depends on what you are encrypting. Remember that the
]M
]> is the base, if the order of the group formed by using M as a base is
]> smaller/larger then for any other M then they will have statistical
]> biases in their sub-groups.
]>
]> For example 45 is a primitive generator mod 257, but 44 is not,
]compare
]> the two tables
]>
]> 45^x mod 257
]> 44^x mod 257
]>
]> To get a better idea.
But this is irrelevant to his question. RSA does not take some number
and raise it to an arbitrary power, it takes the message and raises it
to a fixed power (e, which is 17 or 257 or whatever). Since there is an
inverse, each M must map onto a unique other M. Ie the encryption is
simply a permutation of the set of all messages. (Not quite, since if M
is a multiple of p or q then you have problems, but these are a tiny
subset of all possible messages-- of fractional order of 1/p + 1/q
which is tiny.) The output of the encryption of any particular
message will look random. Of course the output of a whole message need
not be random at all. Eg, consider the message of all 1 ( 10^5 of them)
Each block will cleary encrypt to the same output. Ie the output will be
a bunch of blocks each the same. (each block being say 2000 bits long
with a 2000 bit RSA key)
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: The RSA patent and my software
Date: Tue, 09 May 2000 20:59:52 GMT
Tom St Denis wrote:
>
> You guys seem to argue a bunch about it.
>
> I have chosen the mature way todo things is to not use RSA or any RSA
> ciphers until allowed.
>
> So basically I will not use RSA here or there until Sept 21st.
Err.. In a product, of course my Cryptobag (which has the RSA PK alg) is
available off my Canadian website.
Tom
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: F function.
Date: 9 May 2000 17:58:27 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
> For a 8x8 sbox your highest differential should have a probability of
> about 6/256, 14/256 is too high.
It is a bit. I did say it was *just about* low enough. Note that
14/256 < 2^-4. Iterated over 16 rounds (say), this is less than 2^-64.
And yes I know that this is a long way from being a sufficient condition
for security.
The main point is that, doing something vaguely similar to the original
poster's idea, you end up with an S-box which isn't entirely without
merit.
> Try my sboxgen (http://www.tomstdenis.com/sboxgen.c) to make 8x8
> sboxes.
You really are getting to be a bit of a pain with all of your software
ads. I know it's free, but it's still rather tiresome.
Besides, I was attempting to think about designs similar to the orignal
poster's proposal. I've not looked at your program, but I'd guess it
generates random tables rather than ones based on any particularly
deterministic scheme, such as exponentiation mod 257.
> You could try other primitive bases mod 257 and get different sboxes.
I know. But, as you pointed out, I was aware that James Massey had
already done this sort of thing in SAFER. I was interested in constant
exponents rather than constant bases. It's just that my crappy Perl
script was dog-slow and I didn't want it looping over all 8-bit
exponents as well as additive constants and all inputs and differences.
Bleugh.
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: F function.
Date: 9 May 2000 18:00:29 GMT
Runu Knips <[EMAIL PROTECTED]> wrote:
> Mark Wooding <[EMAIL PROTECTED]> wrote:
>
> > If f is both injective and surjective then
> > we say that f is `bijective' and define an inverse function f^-1 such
> > that f(f^-1(r)) = f^-1(f(r)) = r for all r <- R.
Dammit. I meant that f(f^-1(r)) = r for all r <- R and f^-1(f(d)) = d
for all d <- D.
> Oh damned, why do you mathematicans always explain everything in
> such a complicated way ?? *shiver*
I did say at the top that it basically meant `invertible'. ;-)
-- [mdw]
------------------------------
** 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
******************************
