Cryptography-Digest Digest #743, Volume #13 Sat, 24 Feb 01 15:13:01 EST
Contents:
Re: Processing on cyphertext (Ian Woods)
Re: Random numbers from your sound card (Matt Johnston)
Re: ECC implementation (Bob Day)
Re: Any alternatives to PGP? ("Ryan M. McConahy")
RSA - public key exponents and plain text. (Tony L. Svanstrom)
Re: RSA - public key exponents and plain text. (John Savard)
Re: Super strong crypto (William Hugh Murray)
Re: "RSA vs. One-time-pad" or "the perfect enryption" (William Hugh Murray)
Re: super-stong crypto, straw man phase 2 (William Hugh Murray)
Re: Random numbers from your sound card (Tony L. Svanstrom)
Re: Super strong crypto (Nicol So)
Re: Random numbers from your sound card ([EMAIL PROTECTED])
Sources of entropy on MacOS? ([EMAIL PROTECTED])
Re: ECC implementation (Benjamin Goldberg)
Re: RSA - public key exponents and plain text. (Tony L. Svanstrom)
Re: Simple, possibly flawed, stream cipher ("Henrick Hellström")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Ian Woods)
Subject: Re: Processing on cyphertext
Date: Sat, 24 Feb 2001 12:49:08 +0000 (UTC)
[EMAIL PROTECTED] (Kat Hopwood) wrote in
<[EMAIL PROTECTED]>:
>-----BEGIN PGP SIGNED MESSAGE-----
>
>Ian Woods wrote:
>> Is anyone aware of any encryption schemes which allow some
>> (restricted) forms of processing on cyphertext? To make a bit more
>> sense...
>>
>> E(num1,key) * E(num2,key) = E(num1*num2,key)
>>
>> Or in English: performing an operation on two encrypted numbers (num1
>> and num2) creates a new cyphertext which when decrypted is the value
>> of the operation performed on num1 and num2.
>
>The RSA trapdoor function has this property (for multiplication modulo
>the modulus, N):
>
> num1^e * num2^e = (num1*num2)^e (mod N)
>
>However, be very careful - the RSA trapdoor function is not secure on
>its own as an encryption scheme (without using an encoding method, which
>would destroy the multiplicative property). That doesn't mean you can't
>use it, but its security will have to be analysed in the specific
>context of whatever protocol it is being used in. What exactly is the
>application?
There is no real application. It's a theoretical side line I stumbled
across whilst doing something else to do with modular arithmetic. I'm just
finding it interesting! I have rationalised an application however.
I don't like thin clients... the security problems are quite phenomonal.
Running code on the cleint side and getting encrypted data from a remote
file server is fairly secure.. but from a lot of hot air I've been hearing
about it recently it is intended that some processing (if not lots of
processing) might be done server side. How is it possible to ensure my data
isn't being accessed, giggled over, hacked around with or stole by someone
sitting at the machine (or has broken into the machine) which is running my
word processor for me. This is a very contrived example.. but it
illustrates the point.
Suppose we have an encryption scheme which allows useful processing to
occur on the encrypted data to produce yet more encrypted data. The result
is passed back to you to decrypt and interpret. Not only does it mean the
connection is secure but also that even the server processing the data
cannot tell what the data really is.
The difficulty is creating a secure (or relatively secure) cryptosystem
which allows varied and useful operations to be performed on the
cyphertext.
We do have an advantage however. We don't have a key distribution problem
since we're talking to ourselves. OTP based systems are likely to provide
the maximum security and require little effort (assuming of course you have
a good random number generator). The problem is generating such a system
with a range of operations on the cyphertext which can be used to do /real/
data processing.
I have done some (fairly quick) searches on the web for this kind of thing
and drew up a blank, but I'm interested in finding more cryptosystems where
this kind of property holds in order to develop a system which is good
enough to use.
Ian Woods
------------------------------
From: Matt Johnston <[EMAIL PROTECTED]>
Subject: Re: Random numbers from your sound card
Date: Sat, 24 Feb 2001 21:32:25 +0800
[EMAIL PROTECTED] wrote:
---snip---
> A few weeks ago i came up with an idea: Using sound input to
> generate random numbers. When you record any piece of audio from an
> analogue source to your computer, you will always hear some noise
> that was never present in the original audio, this is the result of
> Electro Magnetic Radiation picked up by the ADC (Analogue to
> Digital Converter) in your sound card. In fact the few lowest bits
> can be cosidered random, as they are full of White radio noise, and
> can be used to generate random numbers.
Damien Miller has already implemented something similar for linux, see
http://www.mindrot.org/code/audio-entropyd.php3
Using the input of a detuned fm radio has been suggested as a good noise
source.
Cheers,
Matt Johnston.
------------------------------
From: Bob Day <[EMAIL PROTECTED]>
Subject: Re: ECC implementation
Date: Sat, 24 Feb 2001 13:45:51 GMT
Benjamin Goldberg wrote:
> I'm currently tring to implement ECC in java, using BigIntegers.
>
> I'll readily admit that I don't understand elliptic curves as well as
> I'd like to, so I'm almost certain that there are mistakes in various
> places throughout the code. Also, I haven't implemented everything yet.
Here's my half done painting, but I'm too lazy to finish it, so
could you do it for me?
-- Bob Day
------------------------------
From: "Ryan M. McConahy" <[EMAIL PROTECTED]>
Crossposted-To: alt.security.pgp,comp.security.pgp.discuss
Subject: Re: Any alternatives to PGP?
Date: Sat, 24 Feb 2001 10:36:34 -0500
=====BEGIN PGP SIGNED MESSAGE=====
Hash: SHA1
- -----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
Now /that/ signature verified properly. :)
You are right. But it is probably more that I just don't like their
commerical ways. I mean, they released the source, and it has been checked.
Ryan M. McConahy
=====BEGIN PGP SIGNATURE=====
Version: 6.5.8ckt http://irfaiad.virtualave.net/
Comment: KeyID: 0xA167F326A5BE3536
Comment: Fingerprint: 838C 815E 5147 2168 5A76 16F1 A167 F326 A5BE 3536
iQA/AwUBOpfVAKFn8yalvjU2EQJx1wCg21ww5MNwTWE+61RU/oM0uSMkHGQAoJvI
fKYEq3Z1CKaC4V6fO4+RmF+O
=81cU
=====END PGP SIGNATURE=====
------------------------------
Subject: RSA - public key exponents and plain text.
From: [EMAIL PROTECTED] (Tony L. Svanstrom)
Date: Sat, 24 Feb 2001 16:00:46 GMT
What size of public key exponents should one look at when creating keys
meant to be used to RSA-encrypt plain text? I've been using 211, good
enough?
/Tony
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: RSA - public key exponents and plain text.
Date: Sat, 24 Feb 2001 16:25:18 GMT
On Sat, 24 Feb 2001 16:00:46 GMT, [EMAIL PROTECTED] (Tony L.
Svanstrom) wrote, in part:
>What size of public key exponents should one look at when creating keys
>meant to be used to RSA-encrypt plain text? I've been using 211, good
>enough?
Some people have used 257, or even 3. (I wonder why they don't use
17.) So, yes, the public exponent can be quite small. (Note that the
ones given here as examples are of the form 2^n+1; this is to make
exponentiation more efficient.)
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: William Hugh Murray <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Super strong crypto
Date: Sat, 24 Feb 2001 16:37:26 GMT
"Douglas A. Gwyn" wrote:
> > Why "so-called," Doug?
>
> Because it's but one, rather weak, exploitation of the idea.
Arguable. If one believes that modern cryptanalysis is about recovering
messages withou the key, then differential cryptanalysis may be a weak
tool. Alternatively, modern cryptography is very powerful or, at least,
cheap.
However, if you believe that modern cryptanalysis is about understanding
and improving cryptography, then differential cryptanalysis is a very
powerful tool. Differential cryptanalysis was used by Biham and Shamir
to demonstrate that Feistel algorithms are very sensitive to the choice
of the s-boxes. Coppersmith reports that IBM used differential
cryptanalysis to help choose the s-boxes for the DES.
>From where this amateur sits, differential cryptanalysis is a very
powerful tool indeed. What am I missing from where I sit?
------------------------------
From: William Hugh Murray <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: "RSA vs. One-time-pad" or "the perfect enryption"
Date: Sat, 24 Feb 2001 17:09:19 GMT
Sundial Services wrote:
> S. wrote:
> > Therefore OTP:s really are unbreakable,
> > provided the pad is truly random and secret.
>
> ... which, of course, is the Achilles heel of this system in practice.
> If you cannot keep a message secret, who's to say that you'll actually
> be able to keep the one-time pad secret, and safe from Mr. Murphy's Law?
>
> The word "perfect" simply does not apply to real-world human enterprises
> of which cryptography of course is one. Conditions are never perfect;
> "ka-ka occurs," and a real system must be able to handle that.
I agree.
Shannon never claimed that the OTP was either perfect or practical. Indeed,
he would have been the first to recognize that it was not. What Shannon
said was that it was provable. That was the only claim that he ever made.
He did not even claim that provable was useful and he certainly did not
claim that it was necessary.
Shannon did not say that the OTP provided perfect security. Rather, he said
that it provided perfect cryptograms. He understood the difference which
seems to me more than can be said for many of those who lay claim to his
idea to make representations about their work.
Nonetheless the idea is useful. It teaches us that as the key gets shorter
than the data, the strength of the mechanism goes down. That if the key is
not random, then the cryptogram is less than perfect. That if the key is
reused, then it leaks information about all the messages. That the OTP is
not practical is only one of the many design limitations that cryptographers
must address every day.
Modern cryptography is not provable or perfect. However, it is
demonstrably, as opposed to provably, good enough, as opposed to perfect.
The idea of perfection may be more valuable than the quest for it and
certainly more than the insistence upon it.
------------------------------
From: William Hugh Murray <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: super-stong crypto, straw man phase 2
Date: Sat, 24 Feb 2001 17:22:20 GMT
David Wagner wrote:
> John Myre wrote:
> >What you are overlooking is the real question: why should
> >we believe that doubling the number of rounds would provide
> >protection to a similar extent? Or tripling, or more?
>
> That's a fair question, but I have a good answer:
>
> For almost all of the publicly known attacks, doubling
> the number of rounds adds substantial protection.
Careful. While it surely adds complexity, it may or may not add
protection. For example, going from 15 to16 rounds for the DES adds
both complexity and protection; going from 16 to 17 adds complexity but
no additional protection. The upper bound of the protection comes from
the brevity of the key. Complexity that exceeds that bound is
gratuitous.
------------------------------
Subject: Re: Random numbers from your sound card
From: [EMAIL PROTECTED] (Tony L. Svanstrom)
Date: Sat, 24 Feb 2001 17:31:06 GMT
Trevor L. Jackson, III <[EMAIL PROTECTED]> wrote:
> At the pet store buy an aquarium with an over-large pump and extra air
> stones for under $50. With this equipment you can create a high speed
> version of the lava lamp.
Poor fish. ;)
/Tony
------------------------------
From: Nicol So <[EMAIL PROTECTED]>
Subject: Re: Super strong crypto
Date: Sat, 24 Feb 2001 13:03:35 -0500
Reply-To: see.signature
After thinking about Douglas Gwyn's proposal some more, I discovered
that while it is an interesting idea, it has several flaws as a design
heuristic.
Unicity distance is a function of key entropy and plaintext redundancy,
but is independent of the cryptographic properties of the cipher. That
being the case, unicity distance is not a good indicator of when keys
should be changed.
Consider this pathological example: truly random (or perfectly
compressed) data is protected by a Vigenere cipher with an alphabet size
of 256 and a period of 16. Because of the lack of plaintext redundancy,
the unicity distance is infinite. Does it mean that the cipher can be
used to safely encrypt a large amount of traffic before a key change?
Obviously not. The cipher is insecure against known-plaintext attacks
and the chaining scheme is not going to fix it.
On the other hand, if plaintext redundandcy is high, using unicity
distance as a guide will likely lead to overly conservative key change
intervals (i.e. keys changed more often than necessary). Modern ciphers
are sufficiently complex that recovering either the plaintext or the key
likely requires more ciphertext than the information-theoretic minimum.
There is also a practical difficulty with using unicity distance.
Unicity distance is a subjective measure (in the sense that it is
relative to the observer). It is possible to estimate a lower bound on
plaintext redundancy, and therefore an upper bound on the unicity
distance. However, estimating the exact unicity distance w.r.t. an
adversary with an unknown amount of partial information is impossible.
For example, suppose a piece of ciphertext decrypts to a grammatical
lover letter in which the sender says she wants to carry the baby of the
recipient. To somebody not knowing the context, it is a perfectly
possible decrypt. To somebody who knows that the communicants are two
(male) priests, the decrypt is certainly implausible.
In Douglas's scheme, traffic encryption keys double as the key
encryption keys of their successors. I think this is a bad idea (and I
think it has been pointed out). Ideally the TEKs, if related to one
another at all, should be so related that knowledge of one (together
with intercepted traffic) would not allow easy derivation of the others.
--
Nicol So, CISSP // paranoid 'at' engineer 'dot' com
Disclaimer: Views expressed here are casual comments and should
not be relied upon as the basis for decisions of consequence.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Random numbers from your sound card
Date: 24 Feb 2001 18:10:55 GMT
In article <XIOl6.4884$[EMAIL PROTECTED]>, Matt Johnston
<[EMAIL PROTECTED]> writes:
>Damien Miller has already implemented something similar for linux, see
>http://www.mindrot.org/code/audio-entropyd.php3
Well, i havent seen it beeing used in any crypto software, althought it's
quite possible that someone thought about this before me.
>Using the input of a detuned fm radio has been suggested as a good noise
>source.
That's right, but the ammount of people that have some kind of a FM reciever
card in their computer or even those that have an fm radio near and can plug
a cable into their soundcard is smaller than the number of people that have a
sound card, i suppose.
Also (i'm not 100% shure that i'm right) i think that random data that was run
throught a FM (\AM\Phase) decoder will loose some of it's randomality.
Viktor P
----- Posted via NewsOne.Net: Free (anonymous) Usenet News via the Web -----
http://newsone.net/ -- Free reading and anonymous posting to 60,000+ groups
NewsOne.Net prohibits users from posting spam. If this or other posts
made through NewsOne.Net violate posting guidelines, email [EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED]
Subject: Sources of entropy on MacOS?
Date: 24 Feb 2001 18:22:22 GMT
Could anyone point me to good sources of entropy on the MacOS? Are there any
rough estimates for these sources?
Thanks,
Erich
----- Posted via NewsOne.Net: Free (anonymous) Usenet News via the Web -----
http://newsone.net/ -- Free reading and anonymous posting to 60,000+ groups
NewsOne.Net prohibits users from posting spam. If this or other posts
made through NewsOne.Net violate posting guidelines, email [EMAIL PROTECTED]
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: ECC implementation
Date: Sat, 24 Feb 2001 18:52:17 GMT
Bob Day wrote:
>
> Benjamin Goldberg wrote:
>
> > I'm currently tring to implement ECC in java, using BigIntegers.
> >
> > I'll readily admit that I don't understand elliptic curves as well
> > as I'd like to, so I'm almost certain that there are mistakes in
> > various places throughout the code. Also, I haven't implemented
> > everything yet.
>
> Here's my half done painting, but I'm too lazy to finish it, so
> could you do it for me?
More like, "Here's my half done painting, is there anything wrong with
how I've done the two point perspective? I'll fill in the other details
once I've gotten that part right." Or maybe, "I'm making a painting of
Theodore Roosevelt in the middle of the forest. I haven't got the trees
and plants done, but do I at least have his face and figure done right?"
If it's irredeemably flawed from the start, then I'll start over, I
guess. If not, I'll finish it.
--
A solution in hand is worth two in the book.
------------------------------
Subject: Re: RSA - public key exponents and plain text.
From: [EMAIL PROTECTED] (Tony L. Svanstrom)
Date: Sat, 24 Feb 2001 19:35:33 GMT
John Savard <[EMAIL PROTECTED]> wrote:
> On Sat, 24 Feb 2001 16:00:46 GMT, [EMAIL PROTECTED] (Tony L.
> Svanstrom) wrote, in part:
>
> >What size of public key exponents should one look at when creating keys
> >meant to be used to RSA-encrypt plain text? I've been using 211, good
> >enough?
>
> Some people have used 257, or even 3. (I wonder why they don't use
> 17.) So, yes, the public exponent can be quite small. (Note that the
> ones given here as examples are of the form 2^n+1; this is to make
> exponentiation more efficient.)
But isn't it safer with a not too small a number?
/Tony
------------------------------
From: "Henrick Hellström" <[EMAIL PROTECTED]>
Subject: Re: Simple, possibly flawed, stream cipher
Date: Sat, 24 Feb 2001 20:45:44 +0100
This attack did not work as well as I had first expected.
I know for a fact that if sbox is a bijective mapping, then the period of
state[0] is 256, the period of state[1] is 512 and the period of state[2]
divides 131072. It seems as if it is possible to select an sbox so that the
period of state[7] is greater than 2**32, but I don't know exactly how great
it might get.
Nevertheless, here is known plain text differential attack that requires a
whole lot of data:
Let k[j] be the byte at position j of the key stream.
Let s[j,i] be the value of state[i] at position i in the key stream.
Let m be the period of state[6].
Let dmk[j] = k[j] xor k[j+m].
Now, since the period of state[i-1] divides the period of state[i], we have
that dmk[j] = sbox[s[j,7]] xor sbox[s[j+m,7]], and we know for a fact that
s[j+1,7]-s[j,7] = s[j+m+1,7]-s[j+m,7]. So if dmk[j] is unequal to dmk[j+1],
we know that dmk[j+1] = sbox[s[j,7]+1] xor sbox[s[j+m,7]+1]. Consequently,
it should not be too hard to derive values of s[j,7] from a sequence of dmk
values. The only problem is that we cannot tell s[j,7] from s[j+m,7], so we
have a 50-50 chance of guessing right. Once this is done, eliminate
sbox[s[j,7]] from each k[j], recalculate dmk where m now is the period of
state[5] and derive state[6] in the same way. Since this method cannot tell
s[j,i] from s[j+m,i], the entire procedure might have to be repeated at most
256 times.
--
Henrick Hellström [EMAIL PROTECTED]
StreamSec HB http://www.streamsec.com
"Henrick Hellström" <[EMAIL PROTECTED]> skrev i meddelandet
news:9775s4$jb3$[EMAIL PROTECTED]...
> Let's see if I got the pseudo code right:
>
> j.1. LET x := 1.
> j.2. FOR i := 0 TO 7 DO:
> j.2.1. IF (x shr i) IS ODD THEN LET state[i] := state[i] + 1.
> j.2.2. LET x := x XOR sbox[state[i]].
> j.3. LET k[j] := x.
>
> Firstly, I'd like to know if result is a one bit or an eight bit value.
> Since x is to be a byte, "keystreambit" appears to be a typo.
>
> Assuming that result is a byte, I'd go about attacking this stream cipher
> using a differential attack, based on the assumption that sbox is key
> independent and known, and on the fact that state[0] is always incremented
> and that state[1],...,state[7] are incremented with a probability of 0.5
and
> otherwise unchanged.
>
> Let y[j] be the number such that, at step j.2.1 and for each i, (x SHR i)
is
> odd if and only if (y[j] SHR i) is odd. Now, for each pair k[j], k[j +1],
> there are exactly 2**(7 + 8) possible expressions
>
> z = b0 * (sbox[s0] XOR sbox[s0+1]) XOR ... XOR b7 * (sbox[s7] XOR
> sbox[s7+1]),
>
> such that b0 = 1. We are only interested in those such that z = (k[j] XOR
> k[j+1]), because if y[j+1] = b0 + b1 * 2 + ... + b7 * 128 and (at step
> j+1.3.) s0 = state[0], s1 = state[1], ... , s7 = state[7], then z = (k[j]
> XOR k[j+1]). Find these combinations for a sequence of k[j]'s, engage in
> some not too complicated puzzle solving, and you will end up with the
> initial value of state[0],...,state[7].
>
> --
> Henrick Hellström [EMAIL PROTECTED]
> StreamSec HB http://www.streamsec.com
>
> "Benjamin Goldberg" <[EMAIL PROTECTED]> skrev i meddelandet
> news:[EMAIL PROTECTED]...
> > I've thought about this idea for the last couple of days, and I haven't
> > yet figured out what kind of weakness(es) it has.
> >
> > uint8 state[8] = { key };
> > uint8 sbox[256];
> >
> > for( i = 0, x = 1; i < 8; ++i )
> > x ^= sbox[ state[i] += (x>>i) & 1 ];
> > keystreambit := x;
> >
> > I can't help but think that there's got to be a flaw here somewhere,
> > since it's so simple, but I can't see where.
> >
> > Also, I'm not quite certain what properties sbox should have --
> > especially if I want the cipher to have the maximum period.
> >
> > One nice thing I can see about this, though: By unrolling and
> > pipelineing, it should take one clock cycle per byte of output.
> >
> > --
> > A solution in hand is worth two in the book.
>
>
>
>
>
>
------------------------------
** 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 by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
