Cryptography-Digest Digest #706
Cryptography-Digest Digest #706, Volume #13 Sun, 18 Feb 01 09:13:01 EST
Contents:
Cryptography FAQ (05/10: Product Ciphers) ([EMAIL PROTECTED])
Crossposted-To: talk.politics.crypto,sci.answers,news.answers,talk.answers
Subject: Cryptography FAQ (05/10: Product Ciphers)
From: [EMAIL PROTECTED]
Reply-To: [EMAIL PROTECTED]
Date: 18 Feb 2001 13:56:41 GMT
Archive-name: cryptography-faq/part05
Last-modified: 94/06/07
This is the fifth of ten parts of the sci.crypt FAQ. The parts are
mostly independent, but you should read the first part before the rest.
We don't have the time to send out missing parts by mail, so don't ask.
Notes such as ``[KAH67]'' refer to the reference list in the last part.
The sections of this FAQ are available via anonymous FTP to rtfm.mit.edu
as /pub/usenet/news.answers/cryptography-faq/part[xx]. The Cryptography
FAQ is posted to the newsgroups sci.crypt, talk.politics.crypto,
sci.answers, and news.answers every 21 days.
Contents:
5.1. What is a product cipher?
5.2. What makes a product cipher secure?
5.3. What are some group-theoretic properties of product ciphers?
5.4. What can be proven about the security of a product cipher?
5.5. How are block ciphers used to encrypt data longer than the block size?
5.6. Can symmetric block ciphers be used for message authentication?
5.7. What exactly is DES?
5.8. What is triple DES?
5.9. What is differential cryptanalysis?
5.10. How was NSA involved in the design of DES?
5.11. Is DES available in software?
5.12. Is DES available in hardware?
5.13. Can DES be used to protect classified information?
5.14. What are ECB, CBC, CFB, OFB, and PCBC encryption?
5.1. What is a product cipher?
A product cipher is a block cipher that iterates several weak
operations such as substitution, transposition, modular
addition/multiplication, and linear transformation. (A ``block
cipher'' just means a cipher that encrypts a block of data---8 bytes,
say---all at once, then goes on to the next block.) The notion of
product ciphers is due to Shannon [SHA49]. Examples of modern
product ciphers include LUCIFER [SOR84], DES [NBS77], SP-networks
[KAM78], LOKI [BRO90], FEAL [SHI84], PES [LAI90], Khufu and Khafre
[ME91a]. The so-called Feistel ciphers are a class of product
ciphers which operate on one half of the ciphertext at each round,
and then swap the ciphertext halves after each round. LUCIFER,
DES, LOKI, and FEAL are examples of Feistel ciphers.
The following table compares the main parameters of several product
ciphers:
cipher | block length | key bits | number of rounds
LUCIFER 128 12816
DES 645616
LOKI 646416
FEAL 64 1282^x, x >= 5
PES 64 128 8
5.2. What makes a product cipher secure?
Nobody knows how to prove mathematically that a product cipher is
completely secure. So in practice one begins by demonstrating that the
cipher ``looks highly random''. For example, the cipher must be
nonlinear, and it must produce ciphertext which functionally depends
on every bit of the plaintext and the key. Meyer [MEY78] has shown
that at least 5 rounds of DES are required to guarantee such a
dependence. In this sense a product cipher should act as a ``mixing''
function which combines the plaintext, key, and ciphertext in a
complex nonlinear fashion.
The fixed per-round substitutions of the product cipher are
referred to as S-boxes. For example, LUCIFER has 2 S-boxes, and DES
has 8 S-boxes. The nonlinearity of a product cipher reduces to a
careful design of these S-boxes. A list of partial design criteria
for the S-boxes of DES, which apply to S-boxes in general, may be
found in Brown [BRO89] and Brickell et al. [BRI86].
5.3. What are some group-theoretic properties of product ciphers?
Let E be a product cipher that maps N-bit blocks to N-bit blocks.
Let E_K(X) be the encryption of X under key K. Then, for any fixed K,
the map sending X to E_K(X) is a permutation of the set of N-bit
blocks. Denote this permutation by P_K. The set of all N-bit
permutations is called the symmetric group and is written S_{2^N}.
The collection of all these permutations P_K, where K ranges over all
possible keys, is denoted E(S_{2^N}). If E were a random mapping from
plaintexts to ciphertexts then we would expect E(S_{2^N}) to generate
a large subset of S_{2^N}.
Coppersmith and Grossman [COP74] have shown that a very simple
product cipher can generate the alternating group A_{2^N} given a
sufficient number of rounds. (The alternating group is half of the
symmetric group: it consists of all ``even'' permutations, i.e
Cryptography-Digest Digest #706
Cryptography-Digest Digest #706, Volume #12 Mon, 18 Sep 00 07:13:00 EDT
Contents:
Re: Double Encryption Illegal? (Paul Schlyter)
Re: Police want help cracking code to find Enigma machine (Anders Thulin)
Re: SDMI Crypto Challenge (Scott Craver)
help hacking Crypt() (Peter Schlosser)
Re: SDMI Crypto Challenge (Matthias Bruestle)
Re: Intel's 1.13 MHZ chip ("Abyssmal_Unit_#3")
Re: More Bleh from a Blahish person. ;) (=?iso-8859-1?Q?H=E5vard?= Raddum)
Re: Tying Up Loose Ends - Correction (Mok-Kong Shen)
Re: question about delastelle cipher in Bauer's book (Mok-Kong Shen)
Re: Frequency Analysis Tables (Mok-Kong Shen)
Re: 20 suggestions for cryptographic algorithm designers (Runu Knips)
Memorizing the CRT (lcs Mixmaster Remailer)
Chosen and known attacks - are they possible ?? ("kihdip")
Re: Comments TC6a please (Runu Knips)
Re: Disappearing Email redux (David Rush)
New Cipher Machine Simulators (Frode Weierud)
Re: question about delastelle cipher in Bauer's book (John Savard)
Algebra, or are all block ciphers in trouble? (John Savard)
From: [EMAIL PROTECTED] (Paul Schlyter)
Crossposted-To: comp.databases.oracle
Subject: Re: Double Encryption Illegal?
Date: 18 Sep 2000 07:40:14 +0200
In article <[EMAIL PROTECTED]>,
wtshaw <[EMAIL PROTECTED]> wrote:
> In article <8q1tfb$bj1$[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Paul
> Schlyter) wrote:
>
>> In article <[EMAIL PROTECTED]>,
>> wtshaw <[EMAIL PROTECTED]> wrote:
>>
>>> When a person uses 3-DES, they are single encrypting with 3-DES.
>>
>> FYI: 3-DES consists of three rounds of DES, using two or three
>> different keys.
>
> That is the definition of a newer algorithm than just plain DES. It
> is not DES.
Well, if you consider any combination of crypto algorithm as "one
single, newer, algorithm", then there is of course no such thing
as "double encryption" or "triple encryption": you've just defined
it as non-existent
--
Paul Schlyter, Swedish Amateur Astronomer's Society (SAAF)
Grev Turegatan 40, S-114 38 Stockholm, SWEDEN
e-mail: pausch at saaf dot se orpaul.schlyter at ausys dot se
WWW: http://hotel04.ausys.se/pauschhttp://welcome.to/pausch
--
From: Anders Thulin <[EMAIL PROTECTED]>
Subject: Re: Police want help cracking code to find Enigma machine
Date: Mon, 18 Sep 2000 06:41:57 GMT
"root@localhost " wrote:
> Anders, Is the initial post with the message text still on the servers
> that you are getting your news from?
You'll find it in the www.deja.com/usenet sci.crypt achive as well.
--
Anders Thulin [EMAIL PROTECTED] 040-10 50 63
Telia Prosoft AB, Box 85, S-201 20 Malmö, Sweden
--
From: [EMAIL PROTECTED] (Scott Craver)
Subject: Re: SDMI Crypto Challenge
Date: 18 Sep 2000 06:52:00 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
>[EMAIL PROTECTED] (Scott Craver) wrote:
>>
>> You can, of course, remove a mark, if you know where it is
>> and how it is embedded. Without that detail, it's not as
>> easy.
>
>If this black box mp3 codec knows where it is, then so will I. Nuff
>said.
I agree with your first sentence but not your second.
>Tom
-S
--
From: [EMAIL PROTECTED] (Peter Schlosser)
Subject: help hacking Crypt()
Reply-To: [EMAIL PROTECTED]
Date: Mon, 18 Sep 2000 07:33:02 GMT
I have a FTP deamon running on one of my servers, that I'd like to
configure user accounts for using Perl scripts. I have examined its
configuration files, and outlined the format the records must be in.
I have one issue that is left to be resolved, and that's the
encryption of the passowrds.
Repeated requests to the author for assistance have gone unanswered.
I suspect the method used is some kind of cipher. Using the user
interface of this FTP server, I can create accounts with known
passwords, and then look at the config files after the passwords have
been ciphered.
All I want to do is copy the method used, so I can set up these
accounts in a more automated way. Some examples of the password
encodings are:
password: "rb17nc01" -> "(v2V'*Tz)o"
password: "65nw52ts" -> "Gnjd^Hjg_w"
password: "35st05ge" -> "H3dtUMAm69"
Can anyone help?
I'm not trying to do anything unethical, am I?
===<>===
Peter Schlosser Peter at NoSpamoni.Signature.Net
"Jack of all
Cryptography-Digest Digest #706
Cryptography-Digest Digest #706, Volume #11 Thu, 4 May 00 18:13:01 EDT
Contents:
Re: Silly way of generating randm numbers? (Tom St Denis)
Re: Silly way of generating randm numbers? ("almis")
Re: Silly way of generating randm numbers? ("almis")
Re: U-571 movie (OT) (David Hamer)
Re: Tempest Attacks with EMF Radiation (Diet NSA)
Re: Tempest Attacks with EMF Radiation (Diet NSA)
Re: RC6 (tm) as a Feistel Cipher (Mok-Kong Shen)
Re: quantum crypto breakthru? (Roger Schlafly)
Re: U-571 movie (OT) (Jim Gillogly)
Re: Silly way of generating randm numbers? ("Tony T. Warnock")
Re: RC6 (tm) as a Feistel Cipher (Tom St Denis)
Re: quantum crypto breakthru? ("Leo Sgouros")
Re: Any good attorneys? (Jerry Coffin)
[ADV] Gartner InfoSec Conference June New Orleans (VictorW318)
Re: Sunday Times 30/4/2000: "MI5 builds new centre to read e-mails on (JCA)
Re: Fixed: Sboxgen tool (Ichinin)
Re: GPS encryption turned off (Paul Koning)
Re: Any good attorneys? (Roger Schlafly)
From: Tom St Denis <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: Silly way of generating randm numbers?
Date: Thu, 04 May 2000 20:16:14 GMT
Richard Heathfield wrote:
>
> Mike Oliver wrote:
> >
> > Richard Heathfield wrote:
> >
> > > Why not? As far as I'm aware, pi passes all mathematical tests for
> > > randomness.
> >
> > In some informal sense that may be true. But I can think of at
> > least one "mathematical test for randomness" that it doesn't
> > pass. Specifically, the linear correlation between the digits
> > of a random number, and the digits of pi, should approach zero
> > as the number of digits considered goes to infinity.
>
> H. There must be more to this than meets the eye. After all, the
> obvious interpretation is:
>
> int test_for_randomness(BIGNUM *control_rndnum, BIGNUM *num_to_test); /*
> linear correlation test function */
>
> result = test_for_randomness(&some_known_random_number, &pi);
>
> If result is false, pi can't be random, because its digits' linear
> correlation with those of some_known_random_number doesn't approach
> zero. Now, how do we establish some_known_random_number? Well, since pi
> has passed loads of tests for randomness, we can use that.
>
> result = test_for_randomness(&pi, &some_known_random_number);
>
> Hey, it returns false. So some_known_random_number isn't random after
> all.
pi may be statistically random, hence a prng, but it's not random at
all. It's C/2r which is known.
Also making terms is not the fastest thing in the world and I doubt it's
a good prng anyways.
Tom
--
From: "almis" <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: Silly way of generating randm numbers?
Date: Thu, 4 May 2000 11:56:44 -0500
Douglas A. Gwyn wrote in message <[EMAIL PROTECTED]>...
|But to actually do this in practice, b would at best be represented
|in a form suitable for symbolic arithmetic based on integer codes
|(since computers cannot represent all real numbers in even a finite
|range). So it seems to boil down to picking a collection of integer
|parameters, which would be limited in practice to a (possibly large)
|finite set of choices that could in principle be tested for a match.
For a method of generating such numbers see:
A. Schonage. The fundamental theorem of algebra in terms of
computational complexity. Preliminary report,
Mathematisches Intitut der Universitat Tubigen. August 1982.
'Splitting the circle'
...al
--
From: "almis" <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: Silly way of generating randm numbers?
Date: Thu, 4 May 2000 11:58:14 -0500
Or just use Mathematica.
...al
--
Date: Thu, 04 May 2000 16:23:19 -0400
From: David Hamer <[EMAIL PROTECTED]>
Subject: Re: U-571 movie (OT)
Paul Matthews does not specifically state that his quoted 'rules'
apply to German navy Enigma operations - so I will here cite
evidence that the Army/GAF did not always have such restrictions
on the daily Enigma settings.
The table [Sonder-Maschinenschlüssel] reproduced as Plate 4 in
Codebreakers, Hinsley & Stripp (eds.) [and elsewhere] tends to
refute Matthews' statement. In a month's worth of daily settings
there are clearly several counter examples to the 'never in the
same place' rules for Walzenlage [e.g. I IV II is followed by
V IV I, and III I IV is even followed by II I IV, etc.]. Counter
examples are also present for the 'never replace a letter with
its neighbour' rule for Steckerverbindungen -
Cryptography-Digest Digest #706
Cryptography-Digest Digest #706, Volume #10 Wed, 8 Dec 99 20:13:02 EST
Contents:
Re: Ellison/Schneier article on Risks of PKI ("Lyal Collins")
low exponent in Diffie-hellman? (jerome)
Re: Synchronised random number generation for one-time pads (Doug Stell)
Re: Cell Phone Crypto Penetrated >> 6.Dec.1999 >> Biryukov & Shamir (Paul Koning)
Re: PCI Cryto Card (Paul Koning)
Re: Johnson Device ("Kasper Pedersen")
Re: NSA should do a cryptoanalysis of AES (SCOTT19U.ZIP_GUY)
Crypt FAQ Comments (section 9.5) (Erik Kraft)
Re: NSA future role? (JCA)
Re: Frequency results of twofish and serpent. (Johnny Bravo)
Re: Frequency results of twofish and serpent. (Johnny Bravo)
Re: NSA future role? (albert)
Re: Random Noise Encryption Buffs (Look Here) (Tim Tyler)
Re: AES cyphers leak information like sieves (Tim Tyler)
Re: Random Noise Encryption Buffs (Look Here) (Tim Tyler)
Re: Solitaire analysis? ("r.e.s.")
Re: NSA should do a cryptoanalysis of AES (Tim Tyler)
Curious PhenomenaRe: High Speed (1GBit/s) 3DES Processor ("Casey")
Re: If you're in Australia, the government has the ability to modify your files.
>> 4.Dec.1999 (Steve K)
From: "Lyal Collins" <[EMAIL PROTECTED]>
Subject: Re: Ellison/Schneier article on Risks of PKI
Date: Thu, 9 Dec 1999 08:16:29 +1100
>Note that I'm not shooting down the whole notion of a PKI. For the most
part,
>I believe that a PKI infrastructure is a Good Thing, because it's a lot
easier
>to keep track of one root certificate and to keep secure one PKI server
than
>it is to secure entire networks full of certificates and servers. But PKI
is
>not the panacea that has been claimed, it is just one tool in the toolkit
for
>keeping a network secure.
I thought that was one point of the article. PKI is not
secure/reliable/trustable (choose the term of your preference) unless the
entire network of machines and certificates are equally secure.
This complexity and effort is roughly equivalent to that required in a
symmetric key system.
>Eric Lee Green [EMAIL PROTECTED]
>Software Engineer Visit our Web page:
>Enhanced Software Technologies, Inc. http://www.estinc.com/
>(602) 470-1115 voice (602) 470-1116 fax
--
From: [EMAIL PROTECTED] (jerome)
Subject: low exponent in Diffie-hellman?
Reply-To: [EMAIL PROTECTED]
Date: Wed, 08 Dec 1999 21:17:41 GMT
i perform a calculation g^x mod p. g=2 and p a prime of 768bits.
The algorithm i used is based on the 'square and multiply'
exponantiation so the smaller x is, the faster is the computation.
as far as i know the only constraint for x is to be 0 > x > p-2.
can i reduce x to 128bits (enougth to prevent a brute force) ?
or there is a special attack for the low exponent ? (some RSA
implementations got issues about that but i don't have the papers
so i can't say if it can be used against Diffie-hellman)
--
From: [EMAIL PROTECTED] (Doug Stell)
Subject: Re: Synchronised random number generation for one-time pads
Date: Wed, 08 Dec 1999 21:03:43 GMT
On Tue, 7 Dec 1999 22:22:02 -, "Charles Meigh"
<[EMAIL PROTECTED]> wrote:
>With regard to one-time pads, which I keep reading as being the most secure
>form of encipherment, it appears that a major problem is the distribution of
>the completely random keys. This is exacerbated by the need for more keys
>for more messages, and larger keyspaces for larger messages (I think).
Correct.
>Would it be practicable to set up a system that creates the random numbers
>for the key from some globally consistent, 'natural' source like, say,
>cosmic radiation readings; the sender and receiver obviously having had
>exchanged brief, secure messages agreeing on exactly when to take these
>key-generating readings? You could then (if i'm thinking right) create as
>many completely secure one-time pads as you like, without the overhead of
>distributing vast amounts of data first, just your synchronising messages.
In the practical world, we frequently run pseudo-random number
generators (PRNG), which are "seeded" by some suitably large secret.
Obviously, this is only as secure as the seed and PRNG
implementation., but this is still very secure.
If seeds are exchanged securely and shared by both parties, then their
respective PRNGs can generate a large amount of identical key stream.
Of course, the two ends need to maintain synchronization and your
protocols have to be designed to facilitate resynchronization without
loss of security.
What you are really asking is whether or not the two parties can
independently create their seeds from some secre
Cryptography-Digest Digest #706
Cryptography-Digest Digest #706, Volume #9 Sat, 12 Jun 99 17:13:02 EDT Contents: Re: Cracking DES (Terry Ritter) Re: Cracking DES (Terry Ritter) Re: Slide Attack on Scott19u.zip (SCOTT19U.ZIP_GUY) Re: Slide Attack on Scott19u.zip ([EMAIL PROTECTED]) Re: Slide Attack on Scott19u.zip (SCOTT19U.ZIP_GUY) Re: Cracking DES (Terry Ritter) Re: Slide Attack on Scott19u.zip (SCOTT19U.ZIP_GUY) Re: Cracking DES (Terry Ritter) Re: Caotic function ([EMAIL PROTECTED]) Re: Slide Attack on Scott19u.zip (SCOTT19U.ZIP_GUY) Re: Slide Attack on Scott19u.zip (Tim Redburn) Re: Slide Attack on Scott19u.zip ([EMAIL PROTECTED]) Re: Slide Attack on Scott19u.zip ([EMAIL PROTECTED]) Re: Slide Attack on Scott19u.zip ([EMAIL PROTECTED]) From: [EMAIL PROTECTED] (Terry Ritter) Subject: Re: Cracking DES Date: Sat, 12 Jun 1999 19:52:11 GMT On 11 Jun 1999 12:46:28 -0700, in <7jrp2k$7hn$[EMAIL PROTECTED]>, in sci.crypt [EMAIL PROTECTED] (David Wagner) wrote: >In article <[EMAIL PROTECTED]>, Terry Ritter <[EMAIL PROTECTED]> wrote: >> >Two other points indicate the assumptions are false. First, >> >the reward is proportional to the intelligence value of the >> >recovered plaintext and not the volume of plaintext. Five >> >percent of the traffic carries much more than five percent >> >of the value, since real traffic is redundant. >> >> Where does this come from? Cite please. Under what assumptions? >> >> The next time you want to read a 200-page book, rip it apart and >> reconstruct the writing from any random 10 pages. So now "reading a >> book" takes only 5% of the time it did. That should be a boon for >> busy executives everywhere! >[...] >I claim that any five consecutive pages from Biham and Shamir's classic >book on differential cryptanalysis would probably be enough to reproduce >most of the ideas, with a bit of work. (Any one of their umpteen pictures >of differential characteristics would likely be enough to give away the >whole game.) *If* we *assume* that an entire book is concerned with a single secret, such that any page can reveal it, *then* we will find, to our great surprise, that any page can reveal it. Now let's try making more realistic assumptions. For example, what percentage of all books fall into such a category? What percentage of all crypto message traffic fall into such a category? And if 5% of the traffic can expose everything, why is it that anyone ever bothers to send the other 95%? >[...] >I don't think this is a particularly contrived example. Is this what >you were asking for? I asked for a citation to the literature where somebody has made such a statement, identified their assumptions, explained their reasoning, and backed it up with evidence. Anybody can handwave that only 5% of the traffic is essentially as good as 100%, but that does not make it true. In special cases it may be true. For the most part, I doubt it is. To imply that it is true is to some extent implying that everyone else (!!!) in the world operates in a haze, repeating everything they say 20 times. --- Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/ Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM -- From: [EMAIL PROTECTED] (Terry Ritter) Subject: Re: Cracking DES Date: Sat, 12 Jun 1999 19:52:19 GMT On Fri, 11 Jun 1999 20:22:21 GMT, in <[EMAIL PROTECTED]>, in sci.crypt [EMAIL PROTECTED] (John Savard) wrote: >[EMAIL PROTECTED] (Terry Ritter) wrote, in part: > >>>I know Terry Ritter disagrees, but I find that as the number >>>of ciphers an enterprise uses increases, the attackers >>>reward/effort ratio goes _up_. He picks off the low hanging >>>fruit. I grant that the ratio goes down if the attacker needs >>>all the encrypted information, but gaining a significant >>>portion of the intelligence value gets easier. > >>Cite it. > >Subject to certain assumptions - which it has already been established >are not true for your proposal - this is a sufficiently obvious result >that it can be demonstrated again. But if those assumptions are *not* true, why do we even bother continuing on this line of reasoning? >If each message is enciphered in only one of the n ciphers, I have proposed that we triple-encipher using different automatically-selected ciphers. For this analysis we can handwave any such "cipher stack" as "a cipher." But note that the cipher stack is inherently as strong as the strongest cipher in the stack (provided we use independent keys). We can, as a sop to critics, fix one of the stack positions to use the cipher people would otherwise use, and t
