Cryptography-Digest Digest #739, Volume #13 Fri, 23 Feb 01 17:13:00 EST
Contents:
Re: super-stong crypto, straw man phase 2 (David Wagner)
Re: super-stong crypto, straw man phase 2 (David Wagner)
Re: Random numbers from your sound card ("Trevor L. Jackson, III")
Re: Super strong crypto (David Wagner)
Re: super-stong crypto, straw man phase 2 ("Trevor L. Jackson, III")
Re: super-stong crypto, straw man phase 2 (John Myre)
Re: Random numbers from your sound card (Jerry Coffin)
Re: "RSA vs. One-time-pad" or "the perfect enryption" (S.)
Re: Powers of Complex Associative Functions (Mok-Kong Shen)
Re: "RSA vs. One-time-pad" or "the perfect enryption" (Sundial Services)
Re: Powers of Complex Associative Functions (Jim Steuert)
Re: Any alternatives to PGP? ("Ryan M. McConahy")
Re: Powers of Complex Associative Functions (Mok-Kong Shen)
Re: Random numbers from your sound card ("Paul Pires")
Really big numbers in C (Taylor Francis)
Re: The Key Vanishes: Scientist Outlines Unbreakable Code, Read it and Weep Boys
(wtshaw)
Re: super-stong crypto, straw man phase 2 ("Henrick Hellström")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: super-stong crypto, straw man phase 2
Date: 23 Feb 2001 19:10:21 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
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. At
the same time, for a fair number of the publicly known
attacks, Gwyn's proposal does not add any security.
If we now assume that unknown attacks will behave roughly
like known attacks, then this suggests that doubling the
number of rounds may be more likely to add substantial
protection than Gwyn's proposal is.
(If we don't assume anything whatsoever about unknown
attacks, I see no scientific reason to believe that *any*
method will or won't add protection, and if we have no
basis to choose between alternatives, we might as well
choose astrology as anything else.)
If I went wrong somewhere, please tell me.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: super-stong crypto, straw man phase 2
Date: 23 Feb 2001 19:15:54 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
John Myre wrote:
>I think his idea is to try to arrive at information-theoretic
>arguments for the security of a cipher mechanism. What do
>we need from a basic block cipher to get "provable" security,
>if we promise to encrypt no more than X bits under any one
>key, and every block as at least Y bits of random data?
Well, Gwyn's proposal is most definitely not secure under the
information-theoretic threat model (where attackers are allowed unbounded
computation), as others have pointed out by noting that exhaustive
keysearch still works no matter how often you change keys.
I fear this will come off sounding negative, and I feel bad, because this
is not my intention. If you think there might be some path to proving
something about Gwyn's proposal, I honestly would like to like to hear
about it, even if it is speculative. However, in the absence of anything
like that, my point is just that there are reasons to be skeptical.
------------------------------
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Random numbers from your sound card
Date: Fri, 23 Feb 2001 19:21:19 GMT
[EMAIL PROTECTED] wrote:
> Also, it could be intresting to try to do the same stuff with TV
> cards, it should give much more data and thus speed the whole
> thing up, not having a TV card and any knowledge about the APIs
> used with them, it's problematic for me to test this out, but
> you're welcome.
You can create massive quantities of unreasonably volatile data for less than
$100. 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. At the computer store buy a parallel port webcam for under $40.
With the extra $10 buy a bright light and shine it on the tank (you want reflection
of the light not transmission, so put it on the same side of the tank as the
camera.
If you have extra cash buy a mirror the size of the tank and put it opposite the
camera and the light. If you are rich buy two mirrors the size of the long side of
the tank, with which you make a hall-of-mirrors, and move the camera & light to the
end of the tank.
Yes, you need to fill the tank with water and plug in the air pump.
Operating the webcam at video speeds gives an unreasonably large volume of volatile
bits. Of course an adversary can chill the output with a clothes pin on the air
line, but for raw TRNG it works for me.
Your Randomness May Vary. ;-)
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Super strong crypto
Date: 23 Feb 2001 19:30:44 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
Douglas A. Gwyn wrote:
>I have in mind is something like this
>example: Block length 512 bits, key length 128 bits, 64 new
>key bits included per block (leaving 448 bits for plaintext).
>These numbers rule out brute-force attacks and known-plaintext
>attacks. I don't think so-called differential cryptanalysis
>can even get a foothold.
Ok, that sounds pretty promising.
However, let me mention that there is an odd scenario where the above
might still be broken by, e.g., differential cryptanalysis.
Imagine a chosen-plaintext, chosen-ciphertext attack. The attacker
convinces the sender to send the encryption of the plaintext P;
she obligingly sends C = E_K(P||K*) on the wire. The attacker now
replaces C with a new ciphertext C' of his choosing; in the case of
differential cryptanalysis, we might use C' = C xor Delta. Now the
recipient receives C' and decrypts it to obtain (P'||K*') = D_K(C').
Finally, the attacker learns P' somehow. Note that the attacker has now
received a pair of texts (P,C), (P',C') where the difference C xor C'
was chosen by the attacker. If there is a differential cryptanalytic
attack on the cipher that can recover the key given only one right pair,
this is sufficient to break the scheme: If (P,C), (P',C') form a right
pair, then the attacker learns K and thus K* and can therefore decrypt
all further traffic from the sender. If (P,C), (P',C') don't form a
right pair, the attacker is stuck unless he can convince the endpoints
that there was a transmission error and that they should "re-synchronize".
The above attack clearly works only under a very restrictive threat model,
and I don't think it is going to be feasible too often in practice, so
if this is the only attack on your proposal, then your proposal seems
to be a real contribution. Nonetheless, I did want to point out that
your proposal does not stop all attacks.
------------------------------
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: super-stong crypto, straw man phase 2
Date: Fri, 23 Feb 2001 19:30:47 GMT
John Myre wrote:
> I think his idea is to try to arrive at information-theoretic
> arguments for the security of a cipher mechanism. What do
> we need from a basic block cipher to get "provable" security,
> if we promise to encrypt no more than X bits under any one
> key, and every block as at least Y bits of random data?
This can be split into distinct issues, one being the elongation of the
unicity distance simply by mixing plaintext with noise, and the other being
the volatility of the keys used to encrypt a data stream. Together they may
have information theoretic synergism, but their fundamental properties appear
to be distinct.
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: super-stong crypto, straw man phase 2
Date: Fri, 23 Feb 2001 13:09:34 -0700
David Wagner wrote:
I think there is a problem with the phrase "information
theoretic". It may be I shouldn't have typed it. I don't
think Doug would accept the unbounded computation threat
model as the only relevant one. He *is* concerned with
concepts involving the amount of available data; he has,
for example, mentioned "unicity distance". Is that concept
meaningless for modern ciphers?
If a cipher can be attacked with one ciphertext block in
a practical way, without even known plaintext, then it is
hopeless. But most modern attacks on decent ciphers
require largish amounts of data. Could you prove that a
given block cipher (triple-DES, say, or Rindael) requires
at least, say, 4 known plaintext/ciphertext pairs to be
broken? Of course, so far as we know, you need way more
than that. Is there any provable minimum?
Then, if you could do such a thing, could you go on to
construct a scheme such as Doug suggests, setting the
amount of "new entropy" overhead, and obtain provable
security, within the assumed computational bounds?
JM
------------------------------
From: Jerry Coffin <[EMAIL PROTECTED]>
Subject: Re: Random numbers from your sound card
Date: Fri, 23 Feb 2001 13:20:06 -0700
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
[ ... ]
> You can create massive quantities of unreasonably volatile data for less than
> $100. 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. At the computer store buy a parallel port webcam for under $40.
> With the extra $10 buy a bright light and shine it on the tank (you want reflection
> of the light not transmission, so put it on the same side of the tank as the
> camera.
Note that if you add salt to the water, you get much finer bubbles.
At least theoretically, with a high-enough resolution camera, you
should be able to get randomness even faster this way...
--
Later,
Jerry.
The Universe is a figment of its own imagination.
------------------------------
From: [EMAIL PROTECTED] (S.)
Subject: Re: "RSA vs. One-time-pad" or "the perfect enryption"
Date: Fri, 23 Feb 2001 20:10:51 GMT
On Wed, 21 Feb 2001 09:14:28 -0700, John Myre <[EMAIL PROTECTED]>
wrote:
> Joseph Ashwood wrote:
> <snip>
> > What you are searching for is purely unbreakable cryptography, even OTP does
> > not qualify (you can given very large quantities of time generate each
> > possible decryption) under your rules.
> <snip>
>
> Huh? Do you mean this? If so, could you please explain?
>
> JM
It is a mistake so simple even I can explain it. For instance, if we
have a ciphertext like this:
"fddRTh6yCv)fg9lyr,ttYeDgEfdW+g5dg8d"
and we look at every possible meaning, using every possible one time
pad, we get several messages, all equally probable. We would get,
amongst others:
"Bob, eliminate Jones next Thursday."
or
"Smith, your cover is blown, return."
or
"This is just a test. Please ignore."
The ciphertext could mean any of the above, and if we were to try all
possible OTP:s, then all of the above and much more, most of it in the
form of gibberish, will show up. Nobody can say which one of all the
messages was the real one. Therefore OTP:s really are unbreakable,
provided the pad is truly random and secret.
S.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Powers of Complex Associative Functions
Date: Fri, 23 Feb 2001 21:28:34 +0100
Jim Steuert wrote:
>
> The function I supplied in the initial post is not a good example
> associative function, as it doesn't reference b1 at all. Sorry about that.
>
> Here are two better examples: C = A OP1 B
>
> c0 = a0*b0 + a2*b1 + a1*b2
> c1 = a0*b1 + a1*b0 + a2*b2
> c2 = a1*b1 + a0*b2 + a2*b0
[snip]
Isn't this C = A * B, where C = [c0, c1, c2], B = [b0, b1, b2]
(both vector) and A is the matrix:
| a0 a2 a1 |
| a1 a0 a2 |
| a2 a1 a0 |
If yes and C and B are the ciphertext and plaintext
respectively and computations are done in Z_n, then the
scheme is a Hill cipher (A must be non-singular). Or have
I misundetstood you?
M. K. Shen
------------------------------
Date: Fri, 23 Feb 2001 13:26:51 -0700
From: Sundial Services <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: "RSA vs. One-time-pad" or "the perfect enryption"
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.
------------------------------
From: Jim Steuert <[EMAIL PROTECTED]>
Subject: Re: Powers of Complex Associative Functions
Date: Fri, 23 Feb 2001 16:19:02 -0500
No, my intention was not that the specific function was a cipher by simply
applying it to plaintext. My intention in a Diffie-Hellman sense is that an
"exponent value" is to be hidden in the result of exponentiating this function.
For example, assume the matrix A, (especially if each cell of the matrix is
itself another (say 3-part) associative function). Raise it to some huge (1024
bit)
exponent. That exponent encodes a secret. The result is another matrix
A-prime = A^k(seed val). What is the possiblity of finding k, ie. of taking the
discrete logarithm based on the power of a matrix (or some arbitrarily complex
associative
function) (i.e. of finding the hidden exponent). First, the seed value must be
a generator of the multiplicative group of the function. I am not aware of any
methods for finding discrete logs base some arbitrary function. (Please let
me know if there are any such methods). I think that these functions may be
simpler to implement than exponentiation.
The second use of this multi-level associative construction is in creating
associative hash functions, which can have as an additional parameter an
exponent as well as a seed value, or can be used, as in Jean Bosset's
application,
as a means of incrementally (additively) hashing a long record or file, because
it is
associative.(although that is a solution in search of a problem)
Also, in that use, xor can be used instead of modular addition. The
constructions I suggested do a lot of "mixing", which is useful for hashing.
-Jim Steuert
Mok-Kong Shen wrote:
> Jim Steuert wrote:
> >
> > The function I supplied in the initial post is not a good example
> > associative function, as it doesn't reference b1 at all. Sorry about that.
> >
> > Here are two better examples: C = A OP1 B
> >
> > c0 = a0*b0 + a2*b1 + a1*b2
> > c1 = a0*b1 + a1*b0 + a2*b2
> > c2 = a1*b1 + a0*b2 + a2*b0
> [snip]
>
> Isn't this C = A * B, where C = [c0, c1, c2], B = [b0, b1, b2]
> (both vector) and A is the matrix:
>
> | a0 a2 a1 |
> | a1 a0 a2 |
> | a2 a1 a0 |
>
> If yes and C and B are the ciphertext and plaintext
> respectively and computations are done in Z_n, then the
> scheme is a Hill cipher (A must be non-singular). Or have
> I misundetstood you?
>
> M. K. Shen
------------------------------
From: "Ryan M. McConahy" <[EMAIL PROTECTED]>
Crossposted-To: alt.security.pgp,comp.security.pgp.discuss
Subject: Re: Any alternatives to PGP?
Date: Fri, 23 Feb 2001 15:25:55 -0500
=====BEGIN PGP SIGNED MESSAGE=====
Hash: SHA1
I myself haven't ever really trusted NAI. I used to use the pgpi.org
versions, but then I found out about CKT. They're much better. They feel
more 'user friendly'.
=====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/AwUBOpbHUKFn8yalvjU2EQIY/wCfYYVYFs99VC4KvflmQFUYlPBryvAAnjpw
D3E49DGyP/obQzicY17Mffcs
=4V1g
=====END PGP SIGNATURE=====
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Powers of Complex Associative Functions
Date: Fri, 23 Feb 2001 22:17:05 +0100
Jim Steuert wrote:
>
> No, my intention was not that the specific function was a cipher by simply
> applying it to plaintext. My intention in a Diffie-Hellman sense is that an
> "exponent value" is to be hidden in the result of exponentiating this function.
> For example, assume the matrix A, (especially if each cell of the matrix is
> itself another (say 3-part) associative function). Raise it to some huge (1024
> bit)
> exponent. That exponent encodes a secret. The result is another matrix
> A-prime = A^k(seed val). What is the possiblity of finding k, ie. of taking the
> discrete logarithm based on the power of a matrix (or some arbitrarily complex
> associative
> function) (i.e. of finding the hidden exponent). First, the seed value must be
> a generator of the multiplicative group of the function. I am not aware of any
> methods for finding discrete logs base some arbitrary function. (Please let
> me know if there are any such methods). I think that these functions may be
> simpler to implement than exponentiation.
>
> The second use of this multi-level associative construction is in creating
> associative hash functions, which can have as an additional parameter an
> exponent as well as a seed value, or can be used, as in Jean Bosset's
> application,
> as a means of incrementally (additively) hashing a long record or file, because
> it is
> associative.(although that is a solution in search of a problem)
> Also, in that use, xor can be used instead of modular addition. The
> constructions I suggested do a lot of "mixing", which is useful for hashing.
Could you give a very tiny numerical example to ease
understanding? Thanks.
M. K. Shen
------------------------------
From: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Re: Random numbers from your sound card
Date: Fri, 23 Feb 2001 13:25:53 -0800
Trevor L. Jackson, III <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> [EMAIL PROTECTED] wrote:
>
> > Also, it could be intresting to try to do the same stuff with TV
> > cards, it should give much more data and thus speed the whole
> > thing up, not having a TV card and any knowledge about the APIs
> > used with them, it's problematic for me to test this out, but
> > you're welcome.
>
> You can create massive quantities of unreasonably volatile data for less than
> $100. 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. At the computer store buy a parallel port webcam for under $40.
> With the extra $10 buy a bright light and shine it on the tank (you want reflection
> of the light not transmission, so put it on the same side of the tank as the
> camera.
>
> If you have extra cash buy a mirror the size of the tank and put it opposite the
> camera and the light. If you are rich buy two mirrors the size of the long side of
> the tank, with which you make a hall-of-mirrors, and move the camera & light to the
> end of the tank.
>
> Yes, you need to fill the tank with water and plug in the air pump.
>
> Operating the webcam at video speeds gives an unreasonably large volume of volatile
> bits. Of course an adversary can chill the output with a clothes pin on the air
> line, but for raw TRNG it works for me.
>
> Your Randomness May Vary. ;-)
Do fish improve the output (by occulting the
bubbles according to an incomprehensible
rational) ?
Paul
------------------------------
From: Taylor Francis <[EMAIL PROTECTED]>
Subject: Really big numbers in C
Date: Fri, 23 Feb 2001 15:43:46 -0600
Anyone know how to handle really bug numbers in C? I'm talking
1024-4096 bit numbers...my compiler only handles 64 bit (that I can
tell...)
Thanks
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: The Key Vanishes: Scientist Outlines Unbreakable Code, Read it and Weep
Boys
Date: Fri, 23 Feb 2001 15:35:01 -0600
In article <[EMAIL PROTECTED]>, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
>
> On the whole, I surmise that it was the journalism of
> the NY Times that has created a flare/claim of (absolute)
> 'unbreakability' of the scheme and has consequently
> caused much unnecessary discussions/misinterpretations.
>
> M. K. Shen
It seems like a companion idea to the winnowing concept, nothing really
new in either. And, I would hold both of these people in high regard, and
never want to punish anyone from saying, "What if," even if they are far
form the first to think such a thought.
--
Better to pardon hundreds of guilty people than execute one
that is innocent.
------------------------------
From: "Henrick Hellström" <[EMAIL PROTECTED]>
Subject: Re: super-stong crypto, straw man phase 2
Date: Fri, 23 Feb 2001 23:02:59 +0100
"John Myre" <[EMAIL PROTECTED]> skrev i meddelandet
news:[EMAIL PROTECTED]...
> If a cipher can be attacked with one ciphertext block in
> a practical way, without even known plaintext, then it is
> hopeless. But most modern attacks on decent ciphers
> require largish amounts of data. Could you prove that a
> given block cipher (triple-DES, say, or Rindael) requires
> at least, say, 4 known plaintext/ciphertext pairs to be
> broken? Of course, so far as we know, you need way more
> than that. Is there any provable minimum?
The provable (absolute) minimum, based only on the assumption that the key
is recovered by means of cryptoanalysis, is the amount of chosen plain text
required for a brute force key search to succeed. This minimum is usually
equal to the size of the key. If I am not mistaken, e.g. Rijndael with a
256-bit key would always be broken by such a theoretical attack given
exactly two blocks of known plain text. I don't know if it would take three
or maybe four blocks of known plain text to break TwoFish because of it's
loss of internal data caused by the shift left by one operation.
I base these conclusions on the observation that relatively small portions
of internal key data could be used to unequivocally determine the key. For
instance, it seems to be common practice to set up S-boxes so that only one
value S(x) or at most two values S(x), S(y) unequivocally determines the
entire S-Box. The only non-static substitution in Rijdael seems to be
xor-operations with internal key data.
Let's just say that I would find it somewhat comforting to find out that I
was completely wrong about this.
--
Henrick Hellström [EMAIL PROTECTED]
StreamSec HB http://www.streamsec.com
------------------------------
** 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
******************************
