Cryptography-Digest Digest #787, Volume #13 Sat, 3 Mar 01 12:13:00 EST
Contents:
Re: How good is the KeeLoq algorithm? (S�ren A.M�ller)
Re: Super strong crypto (John Savard)
Re: Super strong crypto (John Savard)
Re: Super strong crypto (John Savard)
Re: philosophical question? (John Savard)
Re: philosophical question? (John Savard)
Re: Again on key expansion. ("Cristiano")
Re: => FBI easily cracks encryption ...? (William Hugh Murray)
Re: How good is the KeeLoq algorithm? (Fetcher)
Re: philosophical question? (SCOTT19U.ZIP_GUY)
Re: philosophical question? (Joe H. Acker)
Re: Completly wiping HD (nemo outis)
Re: Text of Applied Cryptography (Taylor Francis)
Re: => FBI easily cracks encryption ...? (Nemo psj)
----------------------------------------------------------------------------
From: S�ren A.M�ller <[EMAIL PROTECTED]>
Subject: Re: How good is the KeeLoq algorithm?
Date: Sat, 3 Mar 2001 13:50:39 +0100
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
says...
> I have looked at the KeeLoq algorithm in detail, and it appears to be
> as secure as any 64-bit key 32-bit block algorithm could be. It is
> well-suited for remote keyless entry, but for little else because
> it is so very slow, using over 500 rounds.
Thanks for the info.
Yes, it is slow (28ms for decoding on a 4MHz (1 MIPS) PIC
microcontroller), but it only needs something like 16 bytes of RAM (8 for
key, 4 for data, 4 for misc) and 4 bytes of static look-up table (32
bits) so it can be fitted into the smallest PIC microcontroller.
Do you know if it has any weak keys?
And if it is significantly degraded by use of fewer rounds? (I guess it
is otherwise they would have used fewer rounds - right?)
--
S�ren A.M�ller
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Super strong crypto
Date: Sat, 03 Mar 2001 13:28:52 GMT
On Thu, 15 Feb 2001 18:09:12 GMT, "Douglas A. Gwyn"
<[EMAIL PROTECTED]> wrote, in part:
>Here is a "straw man" block cipher design for you all to analyze:
>The last PT block before the unicity distance is reached contains
>a newly generated random key to replace the one currently in use.
>It's a new form of "chaining" mode, if you wish.
This is essentially equivalent to double encryption.
Think of the message as having the form:
Plaintext: PM1 K1 PM2 K2 PM3 K3
Enciphered by: K0 K0 K1 K1 K2 K2
Yielding: CM1 CK1 CM2 CK2 CM3 CK3
Because K0 is shorter than the redundancy in PM1, if the message
stopped there, one would have an ambiguous decipherment. (K0 is still,
though, shorter than PM1 in total, so this cipher depends on the
compression applied to the plaintext to work, as pictured here.)
The legitimate decipherer, however, only has to know K0 to read the
entire message.
Thus, what one has is, in addition to
CM1 = E(PM1, K0)
one also has
CM2 = E(PM2, K1) and CK1 = E(K1, K0)
CM3 = E(PM3, K2) and CK2 = E(K2, K1)
so one has enough equations to solve the cipher, given that the
unicity distance is exceeded by PM1 + PM2 + PM3.
Like the "Aryabharata" scheme, though, where the ciphertext is E(P XOR
R, K1) + E(R, K2), it makes things very difficult for the cryptanalyst
to perform the attack on both encipherments simultaneously, perhaps
more difficult than with double encryption.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Super strong crypto
Date: Sat, 03 Mar 2001 13:33:01 GMT
On Fri, 16 Feb 2001 23:31:48 GMT, "Douglas A. Gwyn"
<[EMAIL PROTECTED]> wrote, in part:
>Nicol So wrote:
>> Interesting idea, but I see some practical difficulties. If the cipher
>> is inside some general-purpose communication mechanism that makes no
>> assumption about the traffic, how does it know when to switch to a new
>> key?
>That would be specified e.g. in a header. In fact real cryptosystems
>often have expiration criteria associated with their keys. What I
>described was an attempt to avoid introducing a big key distribution
>problem for such a system.
One assumes, though, that this system is not intended for use in a
system so general-purpose that it switches to a new key more often for
users transmitting uncompressed data and so on. That would indeed be
impractical under existing technology. While the NSA may well have
things we don't, trusting an automated assessment of redundancy levels
in plaintext as part of the basis for the security of a cryptosystem
is something they're unlikely to even consider, even if they can do
that better than the open world, so I think anything like *that* is
outside any state-of-the-art likely to be found anywhere.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Super strong crypto
Date: Sat, 03 Mar 2001 13:43:22 GMT
On 21 Feb 2001 03:49:24 GMT, [EMAIL PROTECTED] (David Wagner)
wrote, in part:
>I must admit that I don't yet understand the point of this proposal.
>Standard practice today is, when a symmetric key K is about to expire,
>to generate a new symmetric key K' and send K' using the same channel
>(typically secured with public-key crypto) that K was sent over.
>Since symmetric keys are assumed to be good for encryption of a huge
>amount of plaintext -- say, billions of bytes, for typical modern ciphers,
>at a minimum -- the cost of the public-key operation for transmitting
>a new key is amortized over many bytes and thus is typically negligible.
>Note that current practice is at least as secure as Gwyn's proposal
>(and possibly more secure). Moreover, with today's key lifetimes and
>cost of public-key operations, I see little reason to prefer one over
>the other on performance grounds.
The difference is: "about to expire" for a symmetric key is *not*
defined as "when the unicity distance is reached".
So he is advocating changing keys _much more often_; changing keys
when information-theoretic security (would have been) retained for the
key (had it been used in isolation, instead of within this scheme)
instead of far less often, depending on the work-factor security of
the cipher in use.
The scheme is similar to the idea of sending messages this way:
send E(P xor R, K1) and E(R, K2) and that way, both encryptions are of
a totally random sequence.
It's equivalent to double encryption, but it may be harder to couple
the simultaneous attack against both encryptions together than it
would be to attack a double encryption.
I think this is an "old idea", but I don't know of any results which
examine in detail this question:
which is harder, given the ciphertext-only case:
cracking E(E(P,K1),K2)
cracking E(P xor R, K1) + E(R, K2)
cracking E(P1,K1)+E(K2,K1)+E(P2,K2)+E(K3,K2)+E(P3,K2)+...
where P1+P2+P3... = P, and the redundancy of each segment of P is
shorter than the key size.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Crossposted-To: sci.crypt.random-numbers,de.sci.informatik.misc,sci.math
Subject: Re: philosophical question?
Date: Sat, 03 Mar 2001 13:48:23 GMT
On Wed, 28 Feb 2001 11:36:49 +0100, Peter Osborne
<[EMAIL PROTECTED]> wrote, in part:
>Can there be a fundamental difference between pseudo-randomness and
>real randomness (e.g. generated by radioactive decay or thermal
>noise), especially under these aspects mentioned above?
>From the cryptographic point of view, there is a very fundamental
difference between pseudo-randomness and real randomness.
For a pseudo-random sequence, there are only as many possibilities as
there are possible values for the initial seed.
For a real random sequence, every combination of bits the length of
the sequence is possible.
So a pseudo-random sequence, once one has a chunk of it the size of
the seed, can be - even if it is very difficult to do so - predicted
from then on. Stream cipher: crackable; one-time pad: not crackable.
A true random sequence is incompressible; nothing will specify it
except the entire sequence itself.
A pseudo-random sequence is specified by its seed and its algorithm,
so it does have much smaller information content.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Crossposted-To: sci.crypt.random-numbers,de.sci.informatik.misc,sci.math
Subject: Re: philosophical question?
Date: Sat, 03 Mar 2001 13:52:04 GMT
On 28 Feb 2001 08:45:06 -0600, Andre van Straaten
<[EMAIL PROTECTED]> wrote, in part:
>Example:
>If I take a bit stream from a Geiger counter and set definitely one bit
>every 1 MB, e.g., to transmit hidden information, I don't see any method
>which tells me that the original bit stream is random, but the tampered
>one is not.
It's true that there is no method that can solve any cipher. If you
already know the answer, though, you can show that a bit stream is not
random. Thus, the person who knows which bit in each megabyte has the
secret message, by reading his message, shows the tampered stream is
not.
That's why it is instead said that randomness depends on how a bit
stream is produced, not the actual bits, because that's the only way
we are able to determine if randomness exists. If we make the bit
stream with a Geiger counter, then we know there *is* no hidden answer
for finding a message within the bit stream.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: "Cristiano" <[EMAIL PROTECTED]>
Subject: Re: Again on key expansion.
Date: Sat, 3 Mar 2001 15:13:00 +0100
> > I have thought about to use the elliptic curve (as posted in other
message),
> > but I have not received any comment...
>
> What's the advantage of this method over the method described by Schneier?
Schneier in his paper "Secure Applications of Low-Entropy Keys" (paragraph
4.1 "Time to Compute") says:
"the theorem says that iterating the hash function 2^t times adds at least
t-1 bits of extra "strength" to the key.";
Benjamin Goldberg (in this thread) says:
"You are adding (4 + log2(512)), or 13 effective bits of entropy." (with my
method, but I'd like to know the proof).
If "strength" of Schneier and "entropy" of Benjamin are the same thing, with
Schneier's method I need 2^(13+1) iterations to add 13 bits of entropy, with
my method I need only 16 iterations.
In my new implementation (with miracl), Schneier's method takes 1.26 s, my
method takes only 0.079 s (about 16 times faster).
Moreover, a single iteration of a brute force attack will takes (in my
implementation) only 76 micro seconds for the Schneier's method and 5 ms for
my method: to try 1,000,000 keys with the former it will takes only 76 s,
but with the latter it will takes 1h23m!
Cristiano
------------------------------
From: William Hugh Murray <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Crossposted-To: alt.security.pgp,talk.politics.crypto
Subject: Re: => FBI easily cracks encryption ...?
Date: Sat, 03 Mar 2001 14:18:01 GMT
kroesjnov wrote:
> > > Could not agree more with you.
> > > Although I am not an American, I would not mind, if the BVD (Dutch
> National
> > > Intellegence service) would have this abillity.
> > > I think they (Like any other country`s national intellegence service)
> should
> > > try their very best, to make this possible...
> >
> > Were you in Holland when the Nazi's invaded and took over all the police
> > records?
>
> (Well this is going to be a touchy discussion...)
>
> Nope, I was not there.
> I am only 19 years old.
>
> I think this is slightly off the topic, but I will run with it any way:
>
> I assume you are refering to the fact, that the Dutch administration (and
> with that, the National Intellegence agency) on people was to good organized
> (Thinks like race and religion where also archieved, so that the Nazi`s had
> a very easy job, finding out who was off jewish origin).
I attended a privacy conference in Europe in the early 70's. I remember that
the Surete' knew who slept in every bed in France every night. The Europeans
were busy passing privacy legislation to protect the citizens from one another
while the police were busy building dossiers on their citizens, just doing what
bureaucrats do. The delegates to the conference seemed to see no connection
between these things. The exception were the Dutch. They remembered the
invasion and the use of records kept for one reasonably benign purpose being
used by "legitimate" authority for another. A generation earlier the French
were killing one another in retribution for cooperating with the legitimate
authorities. Months before that, the legitimate government authority was
chasing down and killing the resistance, not to mention men, women, and children
of the illegal religion. A generation ago the citizens of East Germany were
cooperating with the legitimate authority to keep records on one another's
personal lives.
> If you want my opinion on this:
Not particularly. The young are almost universally on the side of what they
believe to be that of "truth and justice;" it is part of your beauty. Those of
us who have been around a few generations understand that it is easier to be on
the side of truth and justice than it is to know where that side is.
> This was wrong afcourse, and so history has
> teached us (The hard way).
If history teaches us anything, it is that her lessons are not persistent. The
newest generation often forgets them and is forced to recapitulate them.
> Yet I do not see the connection to the ability off a Secret Service being
> abble to crack an encrypted message (With effort afcourse), So that
> Terrorist could be intercepted, who are going to bomb some building in The
> Netherlands, or any other Country in the World.
The connection is subtle. What concerns us is that government is a big and
clumsy tool. It is difficult to control under the best of circumstances. One
man's terrorist is another's freedom fighter. It is necessary to order but not
necessarily orderly. It is difficult to tell, much less preserve, the
difference between the legitimate authority of government and tyranny. The
governed cannot always recognize it from the outside and the governing seem to
have an even greater difficulty seeing it from the inside. They become confused
between their doing what is legitimate and that what they are doing is
legitimate.
> Did I assume wrong, on what you are referring to? Or do I just missed the
> point you were trying to make?
If you had been there, the point would have been obvious. Because you were not,
it was poorly made.
> Please be patience with me, I may be slow off understanding...
You may trust that we will be patient with you. It is usually the young who
lose patience first.
> "Wisdom lies not in obtaining knowledge, but in using it in the right
> way".....
....and in the ability to recognize the right way in a novel situation.
While the young tend to believe that the world has always been as they found it,
it is in the nature of being young that all situations are novel. The study of
history can help. History are the stories we tell ourselves about who we are
and we got to be this way.
>
>
> kroesjnov
> email: [EMAIL PROTECTED] (remove nov to reply)
> UIN: 67346792
> pgp fingerprint: 4251 4350 4242 7764 80DA DB1C E2B2 850A DF15 4D85
William Hugh Murray
------------------------------
From: [EMAIL PROTECTED] (Fetcher)
Subject: Re: How good is the KeeLoq algorithm?
Reply-To: [EMAIL PROTECTED]
Date: Sat, 03 Mar 2001 15:47:11 GMT
On Sat, 3 Mar 2001 13:50:39 +0100, S�ren A.M�ller
<[EMAIL PROTECTED]> wrote:
>
>Yes, it is slow (28ms for decoding on a 4MHz (1 MIPS) PIC
>microcontroller), but it only needs something like 16 bytes of RAM (8 for
>key, 4 for data, 4 for misc) and 4 bytes of static look-up table (32
>bits) so it can be fitted into the smallest PIC microcontroller.
>
>Do you know if it has any weak keys?
>And if it is significantly degraded by use of fewer rounds? (I guess it
>is otherwise they would have used fewer rounds - right?)
I'm not qualified to comment on the weak keys. Yes, they
need to use lots of rounds because one round does so little.
Every bit of the input block affects every other bit after 39
rounds, and it takes 64 rounds to use every bit of the key.
As you can guess from these numbers, they operate on one bit
at a time. In terms of confusion and diffusion, they are
heavy on the confusion and weak on the diffusion, which they
make up for by using so many rounds.
-Fetcher
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Crossposted-To: sci.crypt.random-numbers,de.sci.informatik.misc,sci.math
Subject: Re: philosophical question?
Date: 3 Mar 2001 15:52:55 GMT
[EMAIL PROTECTED] (John Savard) wrote in
<[EMAIL PROTECTED]>:
...
>For a real random sequence, every combination of bits the length of
>the sequence is possible.
>
Yes I agree every combination possible.
>So a pseudo-random sequence, once one has a chunk of it the size of
>the seed, can be - even if it is very difficult to do so - predicted
>from then on. Stream cipher: crackable; one-time pad: not crackable.
>
>A true random sequence is incompressible; nothing will specify it
>except the entire sequence itself.
>
Not true!! Since as you stated above any sequence is possible
this makes no since. What does make sense is to say that the averge
length of the compressed sequence will not be shorter. Sometimes
its longer sometimes shorter but on average it will not be longer.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
Scott famous encryption website **now all allowed**
http://members.xoom.com/ecil/index.htm
Scott LATEST UPDATED source for scott*u.zip
http://radiusnet.net/crypto/ then look for
sub directory scott after pressing CRYPTO
Scott famous Compression Page
http://members.xoom.com/ecil/compress.htm
**NOTE EMAIL address is for SPAMERS***
I leave you with this final thought from President Bill Clinton:
------------------------------
From: [EMAIL PROTECTED] (Joe H. Acker)
Crossposted-To: sci.crypt.random-numbers,de.sci.informatik.misc,sci.math
Subject: Re: philosophical question?
Date: Sat, 3 Mar 2001 17:06:04 +0100
George Greene <[EMAIL PROTECTED]> wrote:
> Every fully-specified sequence is equiprobable.
> The differences in probability come from different-sized
> GROUPS of sequences.
I feel somewhat dumb that this didn't pop into my mind. Thank you for
your patience explaining it.
> There is, for example, only 1 sequence of all 1's or all 0's.
> But there are many many sequences with equal numbers of 1s
> and 0's. So the probability that the sequence will have matching
> numbers of 1s and 0s is a lot higher than that it will be all
> 1s or all 0s. But every individual sequence has the same probability.
What I still don't grasp is how you can make the difference: As there
are many more possible sequences with equal numbers of 1's and 0's, any
individual sequence that occurs should more probably contain many 0's
and 1's mixed up as contain only 1's. I understand the group argument,
but I don't understand why it *doesn't* follow from it that it's less
probable that an individual occurance of a sequence with only 1's occurs
than an individual occurance of the usual 1's and 0's in a sequence.
The claim that an individual sequence of only 1's is as probable as a
"usual" random sequence seems to contradict directly to the group
argument. Could anyone who has the time please point me in the right
direction? Does it have something to do with infinite vs. finite random
sequences?
Regards,
Erich
------------------------------
From: [EMAIL PROTECTED] (nemo outis)
Subject: Re: Completly wiping HD
Date: Sat, 03 Mar 2001 16:42:37 GMT
You've got it right. Even hard disks are so cheap nowadays that "data wiping"
by destruction is feasible.
Regards,
In article <97qber$[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Guy
Macon) wrote:
>Albert P. Belle Isle wrote:
>
>Good info! thanks!
>
>I use a floppy disk and a fireplace to wipe my info.
>Let them try to recover *THOSE* bits!
>
>
>
>>Forensic disk data recovery attacks attempt to read "deleted" (or
>>inadequately overwritten) magnetically stored data on your disk either
>>
>>(1) through its drive controller connector, using PC-hosted software;
>>(2) through its drive heads, bypassing the disk's controller circuits;
>>or
>>(3) directly on each disk platter's recording surface in a clean-room.
>>
>>Class 1 ("keyboard") attacks can be mounted directly with forensic
>>software, hosted on your PC or on the attackers' PC. These
>>software-based attack measures can be countered with software-based
>>countermeasures; viz., any kind of disk data overwriting (such as
>>Clearing per DOD 5220.22-M).
>>
>>Class 2 ("laboratory") attacks use special amplifiers and signal
>>processing to extract previously recorded data from under subsequent
>>overwrites. They rely on increased capabilities over the disk's
>>on-board electronics. Sanitizing per DOD 5220.22-M was designed to
>>counter such attacks by increasing the noise-to-signal ratio beyond
>>their capabilities.
>>
>>Many (but not all) INFOSEC people believe that the increased
>>signal-processing sophistication of the on-board controllers required
>>to even read the last-written data has kept Sanitizing ahead in this
>>particular measure/countermeasure race. However, most question the
>>adequacy of Sanitizing in protecting older, lower-density disks
>>(especially diskettes) against the most modern and sophisticated Class
>>2 attacks.
>>
>>Class 3 ("cleanroom") attacks (such as with magnetic force
>>microscopy), are generally considered able to penetrate any software
>>countermeasures, including _any_ kind of overwriting. They are very
>>costly techniques to use to recover the entire image-as-it-used-to-be
>>of an overwritten multi-gigabyte disk, as opposed to a few
>>specifically targeted bytes, however.
>>
>>(Try getting a quote for recovery of overwritten data - not just
>>"reformatted" drive contents.)
>>
>>Nevertheless, any data of sufficient value to intelligence services or
>>comparably-funded adversaries should not have its confidentiality rely
>>upon overwriting countermeasures.
>>
>>The value of your data to the kinds of attackers who can use each
>>class of techniques will determine whether you must counter that
>>class.
>>
>>This is the basis for requiring defense contractors to use Clearing or
>>Sanitizing per DOD 5220.22-M (for re-use or for disposal,
>>respectively) of media containing data classified as Confidential or
>>Secret, while requiring NSA-approved degaussing and destruction for
>>Top Secret media.
>>
>>According to the Navy's Magnetic Remanence Guidebook, a Type II
>>degausser (351-to-750 Oersteds) - preferrably an evaluated model
>>from the NSA's Degausser Products List - is required for Purging hard
>>drives. This removes even the servo tracking data, making the drive
>>totally unusable, as well as suitably free of Classified data.
>>
>>The three armed services' standards for disk data overwriting are
>>NAVSO P5239-26, AFSSI-5020 and AR 380-19, respectively.
>>
>>If your main concern is "keyboard attacks," such as with forensic
>>software or disk sector editors, IBM's free WIPE.EXE utility from
>>their website overwrites all software-accessable sectors with zeros,
>>restoring the disk to "as-new" condition.
>>
>>
>>Albert P. BELLE ISLE
>>Cerberus Systems, Inc.
>>================================================
>>ENCRYPTION SOFTWARE with
>> Forensic Software Countermeasures
>> http://www.CerberusSystems.com
>>================================================
>
------------------------------
From: Taylor Francis <[EMAIL PROTECTED]>
Crossposted-To: alt.anonymous.messages,alt.security.pgp
Subject: Re: Text of Applied Cryptography
Date: Sat, 03 Mar 2001 10:44:20 -0600
Paul Rubin wrote:
>
> There are PDF to text conversion programs around.
Where can I find one?
------------------------------
From: [EMAIL PROTECTED] (Nemo psj)
Date: 03 Mar 2001 16:54:01 GMT
Subject: Re: => FBI easily cracks encryption ...?
Exactly :�
------------------------------
** 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
******************************
