Cryptography-Digest Digest #87
Cryptography-Digest Digest #87, Volume #14Fri, 6 Apr 01 00:13:01 EDT
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: 06 Apr 2001 04:03:56 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., all
permutations which can be written as an even number
Cryptography-Digest Digest #87
Cryptography-Digest Digest #87, Volume #13Fri, 3 Nov 00 18:13:00 EST
Contents:
Re: Rijndael Security (SCOTT19U.ZIP_GUY)
Re: srp-1.7.0 released w/TLS Telnet security, X11 forwarding support (Michael
Erskine)
Re: Visual Basic (Ichinin)
Re: Microsoft's script encoder ("Lefty Louther")
Re: Hardware RNGs ([EMAIL PROTECTED])
Re: Crypto Export Restrictions (Scott Craver)
Re: Microsoft's script encoder (Simon Johnson)
Re: Microsoft's script encoder ("Lefty Louther")
Re: Calculating the redudancy of english? (JPeschel)
Re: how i decode this? ("David C. Barber")
Re: Calculating the redudancy of english? ("Kristopher Johnson")
Crypto++ 4.0 released, and updated crypto benchmarks (Wei Dai)
Re: Q: Computations in a Galois Field (Mok-Kong Shen)
Re: Q: Computations in a Galois Field (Mok-Kong Shen)
example code for your use (Kenneth Lantrip)
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Rijndael Security
Date: 3 Nov 2000 19:08:17 GMT
[EMAIL PROTECTED] (ajd) wrote in
3a028dcf$[EMAIL PROTECTED]:
How secure is Rijndael when given (most of) the plaintext and the cipher
text? For example if I encrypt a bitmap (and somehow the interceptor
knows its a bitmap), the interceptor then knows that the first block
will decrypt to
42 4D ** ** ** ** 00 00 00 00 36 00 00 00 28 00
where bytes 0-1 are the bitmap identifier
2-5 are the file size (which the interceptor doesn't *quite* know as my
encrypted file will be a multiple of the block size, and vthe plaintext
file may not be)
6-9 reserved and always zero
10-13 is the offset to beginning of bitmap data
14-17 is th header size
Given this information about the plaintext, and given the encrypted
text, can the interceptor work out the key? It seems to me like we are
giving away a bit too much information. Is there a standard to get
around this problem?
regards
andrew
I agree with you especailly if the attacker knows what kind of file
your sending. There are many ways to get a round this problem you could
use MAtts BICOM he takes exactly this kind of header problem in to
condsideration. Since after the compression phase the first 20 K of the
file is whitetened then the CBC mode of Rijndael occurs. Or you
could use compress and use a all or nothing encryption pass like
scott16u to whiten the whole file compressed or not compressed and
then use the blessed AES method supplied in Matts code. THe advantage
of the second is that even a one bit change in the input file changes
the whole file. No matter how long it is.
But if you follow so called experts which may not really care if
your stuff is safe. THey will either give a none bijectiv method
or say same crap that modern ciphers are to hard to break so don't
worry about it.
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: Michael Erskine [EMAIL PROTECTED]
Crossposted-To: comp.security.unix,comp.os.linux.security
Subject: Re: srp-1.7.0 released w/TLS Telnet security, X11 forwarding support
Date: Fri, 03 Nov 2000 14:25:38 -0500
Thomas Wu wrote:
Thomas, thank you.
--
Watch your thoughts; they become words.
Watch your words; they become actions.
Watch your actions; they become habits. -- Frank Outlaw
Watch your habits; they become character.
Watch your character; it becomes your destiny.
--
From: Ichinin [EMAIL PROTECTED]
Reply-To: [EMAIL PROTECTED]
Subject: Re: Visual Basic
Date: Fri, 03 Nov 2000 07:24:28 +0100
Patterson Programming wrote:
Ichinin, your syntax uses a 'variant' data type. There is a risk that VB
would move/copy the data in dynamic memory. That makes 'burning' the key
material unreliable. I prefer to use static numeric arrays for such
purposes.
Perhaps, but have you tried it?
You could even try:
Stuff = Array("1", "2", "3", ... , "N")
For X...next
Value = Cint(Stuff(X))
Next X
Also, performance is at least as high using my implementation.
Yes, but some people are concerned with the _layout_ of your
implementation, after all - the layout of your code is so
much more important than actual performance, isn't it? :o)
(yes, irony is the word of the day...)
Regards,
Ichinin
--
From: "Lefty Louther" [EMAIL PROTECTED]
Subject: Re: Microsoft's script encoder
Date: Fri, 3 Nov 2000 21
Cryptography-Digest Digest #87
Cryptography-Digest Digest #87, Volume #12 Thu, 22 Jun 00 15:13:00 EDT
Contents:
Re: Try it. (John)
Re: Missing Info in the crypto-gram of MR BS (Jack)
Re: MD5 Expansion (Simon Johnson)
Re: Forgot ZIP File password. (pwrecover)
Re: CRC-64 and 128 - Generator Polynomials? (Mike Rosing)
Re: obfuscating the RSA private key (Mike Rosing)
FOR MY NONFANS AND FANS (SCOTT19U.ZIP_GUY)
Re: MD5 Expansion ("Joseph Ashwood")
Re: Encryption on missing hard-drives (David A Molnar)
Re: Try it. (James Pate Williams, Jr.)
Re: Variability of chaining modes of block ciphers (Mok-Kong Shen)
Re: Try it. (James Pate Williams, Jr.)
Re: Try it. (John)
Re: Variability of chaining modes of block ciphers (Mok-Kong Shen)
Re: Variability of chaining modes of block ciphers (Mok-Kong Shen)
Re: Try it. (None)
Re: Try it. (John)
Re: Try it. (John)
breaking encryption - help! (Steve Basford)
Re: Try it. ("Joseph Ashwood")
Subject: Re: Try it.
From: John [EMAIL PROTECTED]
Date: Thu, 22 Jun 2000 10:23:05 -0700
[EMAIL PROTECTED] (Mark Wooding) wrote:
None [EMAIL PROTECTED] wrote:
I can only describe the encryption system in question as
follows:
1. It uses Random #s
2. The outputs of the system pass the statistical tests on the
theorietical and empirical level.
Dilbert: `Our product is beige. It uses electricity.'
Marketroid: `Woah! Brain overload!'
Oh, by the way, those are nowhere *near* being sufficient
conditions for
security. (Using random numbers and passing statistical tests,
I mean.
Beigeness and use of electricity aren't actually necessary.
Some crypto
boxes are blue, for example. ;-) )
Yeah, OK. The only thing I've seen here is, "Give us the source,
and we'll let you know if it's secure." Without the source, all
you can do is brute force it.
Encryption is the oddest field. No other area in software is
filled
with so much hype. I don't think I'm as stupid as some think
I am.
Actually, from where I'm sitting, I think it's remarkably free
of hype.
There's a load of dross, but you just ignore that. Compare the
amount
of hype about things like XML and Java.
True, but there is still a lot of hype.
I mean, if you pick a pass phrase and plaintext and can't
figure out
if the cyphertext is whole without the source code, oh well,
I don't
think I'll get qnywhere.
Nope. You've lost me. I only understand English, French,
German and
Latin.
Maude Merde Du Cu!
I take it you don't bother with pass-phrases, cyphertext, etc.
-- [mdw]
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
--
From: [EMAIL PROTECTED] (Jack)
Subject: Re: Missing Info in the crypto-gram of MR BS
Date: 22 Jun 2000 17:18:51 GMT
[EMAIL PROTECTED] (Andrew Bortz) wrote in
[EMAIL PROTECTED]:
At some level there will be identifying information that an automated
program can use to distinguish a correct decryption from an incorrect
one. And most compression algorithms are defined at a file format level,
leaving the implementation up to the programmer. With algorithms that
rely on searching, there will always be more than one way to compress a
file.
Andrew
I think way are playing with different rules. I am assuming the
attacker has both the encryption program and the compression
decompression programs. Also I am assumming that if you compress
a file B then you always get the same compressed file for compressed (B)
if you don't then you are adding noise and that is an entirely different
can of worms and in my way of thinking would be part of an add on of
encryption where one has to worry about how random.
--
Subject: Re: MD5 Expansion
From: Simon Johnson [EMAIL PROTECTED]
Date: Thu, 22 Jun 2000 10:27:02 -0700
"Scott Fluhrer" [EMAIL PROTECTED] wrote:
Simon Johnson [EMAIL PROTECTED] wrote
in message
news:[EMAIL PROTECTED]...
Good point...
I'll revise my suggestion:
Divide the message into two parts,a,b. do this by taking the
first character and appending it to a, the second character
and
appending it to b, the third character and append this to a,
the
forth character and append it to b. And so on and so
fourth.
Then:
Output = h(a) h(b)
This should now be secure enough, with a 128-bit birthday
attack.
Not particularly. Suppose you know M != M' such that h(M) == h
(M'). If h
has a 128 bit output, this takes no more than O(2**64) work
Then, consider the function f(X) that takes a message X, and
replaces each
character with two of that same character. For example,
f( "I am a message" ) = "II aamm aa mmeeaaggee".
It is clear that f(M) != f(M')
Then, if you apply your hashing mechanism to f(M), f(M'), then
you'll find
the a=b=M, a'=b'=M', and so Output==Output', giving you a
collison.
more than O(2**64) work.
Cryptography-Digest Digest #87
Cryptography-Digest Digest #87, Volume #11 Thu, 10 Feb 00 08:13:01 EST
Contents:
Re: Does hashing an encrypted message increase hash security? (David Hopwood)
Re: Continually Secure Password/Pin (David Hopwood)
Re: Anybody know about this flaw? (Greg)
Re: Anybody know about this flaw? (Greg)
Re: NIST, AES at RSA conference ("Joseph Ashwood")
Re: I'm returning the Dr Dobbs CDROM ("Douglas A. Gwyn")
Re: Strip Security (Gordon Walker)
Re: Anybody know about this flaw? (No Brainer)
Re: Guaranteed Public Key Exchanges (No Brainer)
Re: NIST, AES at RSA conference ("Rick Braddam")
Re: NIST, AES at RSA conference (Alan Braggins)
Re: New standart for encryption software ([EMAIL PROTECTED])
Re: Guaranteed Public Key Exchanges (Roger Gammans)
Persistent vs Non-Per DH for Voice ([EMAIL PROTECTED])
Date: Thu, 10 Feb 2000 05:24:29 +
From: David Hopwood [EMAIL PROTECTED]
Reply-To: [EMAIL PROTECTED]
Subject: Re: Does hashing an encrypted message increase hash security?
=BEGIN PGP SIGNED MESSAGE=
Erann Gat wrote:
Suppose I do the following:
1. Generate a 128-bit MD5 hash of a message.
2. Generate a second 128-bit MD5 hash of the same message encrypted
with (say) Blowfish using an N-bit key.
3. Concatenate the results together to form a 256-bit hash.
Does the resulting 256 bit hash have any more security than the
original 128-bit MD5 hash by itself?
It depends which security property you're looking at:
one-wayness: provably no (just ignore the second half of the hash)
collision resistance: probably yes
second pre-image resistance: probably yes
psuedo-randomness: provably no (if the first half is not pseudo-random
then the hash as a whole would not be considered
psuedo-random)
How much more?
For collision and second pre-image resistance, I've no idea.
What if the Blowfish encryption key is known
It doesn't appear to matter whether the key is known when considering
one-wayness and pseudo-randomness.
For collision and second pre-image resistance, I don't know (but note
that a function that requires secret information to evaluate
typically wouldn't be classified as a hash; it would be classified as
a MAC instead, and those have different security requirements).
- --
David Hopwood [EMAIL PROTECTED]
PGP public key: http://www.users.zetnet.co.uk/hopwood/public.asc
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
"Attempts to control the use of encryption technology are wrong in principle,
unworkable in practice, and damaging to the long-term economic value of the
information networks." -- UK Labour Party pre-election policy document
=BEGIN PGP SIGNATURE=
Version: 2.6.3i
Charset: noconv
iQEVAwUBOKJLUTkCAxeYt5gVAQHYTAf+NbfilZPFbY/3HB5RowJwt/ZhP1dwxUYY
LWegMriXJFXxV8XlGD4GYIA9C4z7Xorzy4FzaZ7vJ/SS99onfHuevLR8VoB+Z+re
tC8AfWVHq8b3FiFGVAHQrp0EAH1e5LIYZKVeroPvETuaY7cnI0hBNv4IQyR/rR4F
1ZNPz5nuwjfNDysUlz5U+O34PfKEFkGv4QK01nywaLOSwSTaG9M7dS5rxtxSTBsL
Qf8K2cO8cMf0GdGAN7lLoQxeZ0KrsLDr89vNT3xrBoiD9tVj3O4xSiBPQ7lGTXfO
h5ANpSTgj94xIjSzNZru06Dwn8pbNT7k3AZ3edpI2t6+iGahMU+3Sg==
=J7aI
=END PGP SIGNATURE=
--
Date: Thu, 10 Feb 2000 06:48:09 +
From: David Hopwood [EMAIL PROTECTED]
Reply-To: [EMAIL PROTECTED]
Subject: Re: Continually Secure Password/Pin
=BEGIN PGP SIGNED MESSAGE=
[EMAIL PROTECTED] wrote:
When creating and using a user/password account on the web why isn't
the following method used:
Client types in user name and password, clients computer sends server
user name and the one millionth iterative one way hash of the password.
Server creates user name and stores said hash.
When logging on first time user sends user name and the 999,999th
iterative hash of the password. Server authenticates by hashing this
and comparing it to last stored hash. On acceptance it allows access to
account and updates servers hashed password to the new 999,999th
iteration.
Next time user logs on he uses the 999,998th iteration and so on.
This protocol was used by a system called S/Key, and is described in
section 3.2 of Applied Cryptography, 2nd ed.
Here are some weaknesses:
- It's possible to do an off-line dictionary attack on the password.
I.e. an attacker can intercept one session and then test likely
passwords off-line.
- If someone impersonates the server, they get a hash which is
password-equivalent (for one use).
- If the user has the same password for more than one server then
the protocol is not secure. (Perhaps this could be fixed by using
the server name as a salt.)
- It's easy to do a denial-of-service attack by causing the user and
server to get out of sync (this can also happen accidentally).
- The protocol doesn't establish a shared secret key between the use
Cryptography-Digest Digest #87
Cryptography-Digest Digest #87, Volume #9Wed, 17 Feb 99 06:13:05 EST Contents: Cryptography FAQ (04/10: Mathematical Cryptology) ([EMAIL PROTECTED]) From: [EMAIL PROTECTED] Crossposted-To: talk.politics.crypto,sci.answers,news.answers,talk.answers Subject: Cryptography FAQ (04/10: Mathematical Cryptology) Date: 17 Feb 1999 10:25:42 GMT Reply-To: [EMAIL PROTECTED] Archive-name: cryptography-faq/part04 Last-modified: 93/10/10 This is the fourth 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: 4.1. In mathematical terms, what is a private-key cryptosystem? 4.2. What is an attack? 4.3. What's the advantage of formulating all this mathematically? 4.4. Why is the one-time pad secure? 4.5. What's a ciphertext-only attack? 4.6. What's a known-plaintext attack? 4.7. What's a chosen-plaintext attack? 4.8. In mathematical terms, what can you say about brute-force attacks? 4.9. What's a key-guessing attack? What's entropy? Reader, beware: This section is highly mathematical. Well, maybe not _highly_ mathematical, but it's got a bunch of symbols and scary-looking formulas. You have been warned. 4.1. In mathematical terms, what is a private-key cryptosystem? A private-key cryptosystem consists of an encryption system E and a decryption system D. The encryption system E is a collection of functions E_K, indexed by ``keys'' K, mapping some set of ``plaintexts'' P to some set of ``ciphertexts'' C. Similarly the decryption system D is a collection of functions D_K such that D_K(E_K(P)) = P for every plaintext P. That is, succesful decryption of ciphertext into plaintext is accomplished using the same key (index) as was used for the corresponding encryption of plaintext into ciphertext. Such systems, where the same key value is used to encrypt and decrypt, are also known as ``symmetric'' cryptoystems. 4.2. What is an attack? In intuitive terms a (passive) attack on a cryptosystem is any method of starting with some information about plaintexts and their corresponding ciphertexts under some (unknown) key, and figuring out more information about the plaintexts. It's possible to state mathematically what this means. Here we go. Fix functions F, G, and H of n variables. Fix an encryption system E, and fix a distribution of plaintexts and keys. An attack on E using G assuming F giving H with probability p is an algorithm A with a pair f, g of inputs and one output h, such that there is probability p of computing h = H(P_1,...,P_n), if we have f = F(P_1,...,P_n) and g = G(E_K(P_1),...,E_K(P_n)). Note that this probability depends on the distribution of the vector (K,P_1,...,P_n). The attack is trivial (or ``pointless'') if there is probability at least p of computing h = H(P_1,...,P_n) if f = F(P_1,...,P_n) and g = G(C_1,...,C_n). Here C_1,...,C_n range uniformly over the possible ciphertexts, and have no particular relation to P_1,...,P_n. In other words, an attack is trivial if it doesn't actually use the encryptions E_K(P_1),...,E_K(P_n). An attack is called ``one-ciphertext'' if n = 1, ``two-ciphertext'' if n = 2, and so on. 4.3. What's the advantage of formulating all this mathematically? In basic cryptology you can never prove that a cryptosystem is secure. Read part 3: we keep saying ``a strong cryptosystem must have this property, but having this property is no guarantee that a cryptosystem is strong!'' In contrast, the purpose of mathematical cryptology is to precisely formulate and, if possible, prove the statement that a cryptosystem is strong. We say, for example, that a cryptosystem is secure against all (passive) attacks if any nontrivial attack against the system (as defined above) is too slow to be practical. If we can prove this statement then we have confidence that our cryptosystem will resist any (passive) cryptanalytic technique. If we can reduce this statement to some well-known unsolved problem then we still have confidence that the cryptosystem isn't easy to break. Other parts of cryptology are also amenable to mathematical definition. Again the point is to explicitly identify what assumptions we're making and prove that they produce the desired results. We can figure out what it means for a particular cryptosystem to be used properly: it just means that the assumptions are valid. The same methodology is useful
