Cryptography-Digest Digest #252, Volume #12 Thu, 20 Jul 00 07:13:01 EDT
Contents:
Re: TAGGED INFORMATION ("Joseph Ashwood")
Re: strength of encryption ("Joseph Ashwood")
Re: Bit Shuffling (Mark Wooding)
RE: Signed Data ("Yo")
Cryptography FAQ (01/10: Overview) ([EMAIL PROTECTED])
Cryptography FAQ (02/10: Net Etiquette) ([EMAIL PROTECTED])
----------------------------------------------------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: TAGGED INFORMATION
Date: Wed, 19 Jul 2000 23:09:45 -0700
> What if the recipient knows but doesnt give it away?
> Or you find the information removed, what are your thought
processes at that
> point?
Umm, at that point it's still called steganography. If the
(unintended) recipient knows, then it's failed
steganography, if the information is removed it is removed
steganography, but both are steganography regardless.
Joe
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: strength of encryption
Date: Wed, 19 Jul 2000 23:20:15 -0700
In the most common sense it is a measure of the strength of
the algorithm against various attacks. Such as DES offers 56
bits of security against almost every known attack, or
Twofish offers a minimum of 128 bits of security against
known attacks. Of course the terminology has been quite
abused by marketting types, such as "Snake Oil Corp offers
billions of bits of security from a small key." In order to
get an accurate measure of the security your algorithm
employs it is wise to submit it to public review (right here
in sci.crypt is actually a good start), that gives a large
number of people the opportunity to review and attack your
algorithm. The proper way is to post a _SHORT_ description
of your algorithm (ie a 128-bit feistel structure using a
512-bit key, with 8x8 s-boxes) and a URL for the
zip/gzip/jar/ps/pdf/txt/etc file, this way people who have
little idea how to examine your algorithm (perhaps someone
particularly knowledgable in pRNGs) would not waste their
time, while the people that do know how to deal with your
type of algorithm are more likely to take a look.
Joe
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Bit Shuffling
Date: 20 Jul 2000 10:31:23 GMT
Jayant Shukla <[EMAIL PROTECTED]> wrote:
> [EMAIL PROTECTED] (Mark Wooding) writes:
>
> >Please read the long thread between myself and Tom St Denis about why
> >bit permutations in ciphers are a bad idea, including differential
>
> Can you back this statement up with something more? A publication?
What more do you want? I've given you the analysis first-hand! The
fact that analysis is or isn't in an expensive publication has no
relevance to whether it's right, valid, etc., or not. If you want it in
print, print it out!
Oh, references for various comments include `The Twofish Encryption
Algorithm', by Ferguson, Hall, Kelsey, Schneier, Wagner, and Whiting,
and `The Block Cipher SQUARE', by Daemen and Rijmen.
> I can give you an example that refutes your claim. Take a look at
> DES. The P-Box based fixed permutation used in each round of DES is an
> example of bit-permutation making a cipher strong.
You've missed the point almost completely. Bit permutation is a
diffusion mechanism, and removing it almost completely destroys DES's
strength because permutation P happens to be the main source of
diffusion in DES.
DES is a bad example, because S o E is noninjective -- in a right pair,
the two inputs have already collided by the time of the permutation, so
there's no way to improve DES's strength against Biham and Shamir's
attack by replacing P with some other operation. (We can see this
because Hamming weight is preserved by a bit permutation, and the output
of the characteristic through DES's F-function has Hamming-weight 0.)
Let's compare two Feistel networks, by way of an example. In each, a
64-bit plaintext, represented in two 32-bit halves (x_0, y_0) is
encrypted in R rounds, each of the form:
x_{i+1} = y_i XOR F(x_i XOR K_i); y_{i+1} = x_i 0 <= i < R
where the K_i are chosen uniformly at random. The ciphertext is the
pair (y_R, x_R), as usual. The keys K_i aren't important in the
following, except in asmuch as they're important for these to be `real'
ciphers.
The function F, which is the same in each round, is defined by
F = D o S, where S is a nonlinear substitution layer and D is a linear
diffusion layer. In each case, S has the same structure: the 32-bit
input z is split into 4 8-bit parts z_0, z_1, z_2, z_3 and the output is
the concatenation of S_0(z_0), S_1(z_1), S_2(z_2), S_3(z_3), where the
S_i are nonlinear bijective substitution tables. (I'll be using
different S-boxes in the two ciphers.)
In the first cipher, which I'll call C-Perm, the operation D is a
bit-permutation: the bits of the input are simply reordered.
In the second, which I'll call C-MDS, the operation D is multiplication
by an MDS matrix over GF(2^8): the input is interpreted as a column
vector of four GF(2^8) elements and premultiplied by an MDS matrix.
Recall the property of an MDS matrix: if the n x n matrix M is MDS, v is
any nonzero n-element column vector, and v' = M v, then the number of
zero elements in v' and v combined is no more than n - 1.
The first thing to note is that the F-functions of both ciphers are
bijective. Thus, there are no `easy' two-round iterative
characteristics.
In C-Perm, I'll assume that the S-boxes are carefully chosen such that
no differential characteristic (that I'll be using) through any S-box
has probability higher than 2^{-7}. From this point of view, the
S-boxes are `ideal'.
In C-MDS, I'll assume that the S-boxes aren't chosen well, and that I
can find differential characteristics with probability 2^{-4} whenever I
need to. Those are seriously grotty S-boxes!
I note here that, in software at any rate, the two ciphers are just as
efficient as each other. In each case, we precompute 8 x 32 tables
T_i(.) which combine the S and D operations, and then combine the
results for each byte of the input z using either (in the case of
C-Perm) logical-OR or (C-MDS) logical XOR. These are equivalently fast
on all modern architectures I know of.
Let's apply differential cryptanalysis to C-Perm. I'll skip the first
round using a characteristic of the form (0, d) ---> (d, 0), which
always works in Feistel networks.
Now let's look at the structure of the F-function. The permutation D
doesn't change Hamming-weight of its input, and because it's GF(2)-
linear it doesn't change Hamming-weight of XOR differences either. This
will be our avenue of attack.
I'll work at a byte level mostly, and I'll be interested in words which
have three zero bytes. Let B_i = { b 2^{8i} | 1 <= b < 256 }, 0 <= i 4,
be the set of 32-bit integers with byte i `active' (i.e., nonzero) and
the other bytes `passive' (zero). I'll use *_i to refer to an arbitrary
element of B_i \union { 0 }.
Now, I'm interested in characteristics of the form (*_i, *_j) --->
(*_j, *_i). There are three cases to consider:
1. *_i = 0. This is a `free ride'. We have (0, *_j) ---> (*_j, 0)
with probability 1.
2. *_i != 0, *_j = 0. Here, we need a characteristic of the form *_i
---> *_k through F, but k is arbitrary.
3. *_i != 0, *_j != 0. Here, we need a characteristic of the form *_i
---> *_j through F, and j is fixed.
I'll assume that the first case doesn't happen except in the first
round, when I'll force the issue by inputting a difference of the form
(0, *_i). This gives me a free round. I'll get a free round in C-MDS
for exactly the same reason.
Now for the tricky bit. I'm going to claim that 2 and 3 will occur with
probability 2^{-7}. If 3 does, then 2 does too, so I'll just deal with
that.
Let's cope with the permutation D first, and let's look at it
backwards. From byte j of the output, there are 8 bits which are
scattered by the permutation. Now, it could be that all 8 of those bits
come from just one of the input bytes, but that wouldn't make D a very
good permutation. The best we can do is take two bits from each input
byte -- that gives maximum diffusion between the bytes.
By my assumption about the idealness of the S-boxes, we have *_i --->
*_i through S with probability 2^{-7} (that's a different *_i on each
side, but the same byte is active, since S doesn't diffuse between
bytes; both *_i are nonzero). Because I want byte j to be active on
output, I want the output *_i to have only bits which are permuted to
byte j active. I don't believe that you can have an S-box with the good
differential properties I'm hypothesizing for the S_i and which won't
allow characteristics with nonzero propbability and selected output
active bits. I believe that this is enough to justify my claim, if not
to prove it.
I can now piece together differentials for C-Perm. I start with a round
of type 1, followed, by a round of type 2, and then R - 2 rounds of type
2 or 3, giving me a probability of 2^{7(1-R)} for the entire cipher.
Let's look at C-MDS. The structure of the F function guarantees that no
characteristics of types 2 and 3 can exist. Instead, let's count active
S-boxes in each round. Let A(d) be the number of active bytes in a
32-bit difference d.
We can bypass the first round by using a characteristic (0, d) --->
(d, 0). The number of active S-boxes in round 2 is equal to the number
of active bytes in d, A(d). In round 3, we have 5 - A(d) active
S-boxes. That's already 5 active S-boxes by the end of round 3.
At this point we've reached a problem. It's conceivable that the
Feistel mixing is reducing the number of active bytes. The degree to
which this happens depends on the key words mixed into the round
function. A reduction of one active byte will occur randomly with
probability 2^{-8}. This is considerably higher than our S-box
differential probability: we're best off putting up with the active byte
and S-box differential than hoping for a byte to be knocked out.
We hence have a lower bound of 5 active S-boxes in every two rounds, or
a probability of 2^{-4}^5 = 2^{-20}. Hence, an upper bound on the
probability of any differential characteristic through the entire cipher
is 2^{10(1-R)}.
If resistance to differential cryptanalysis is our only criterion for
fixing the number of rounds, we need 10 rounds of C-Perm for security,
as opposed to 8 rounds of C-MDS.
> If you remove that operation, you can break DES using only 2^20
> plain-text and cipher-text pairs. Ofcourse, if you don't choose the
> P-Box properly you may still weaken DES, but the point is that DES is
> stronger with P-Box based bit-permutation than without.
Yes. Two points here:
(a) All efficient implementations of the DES in software combine the
bit permutation P with the substitution tables into a collection
of 6 x 32 SP tables. Your technique is irrelevant to DES
implementation.
(b) If you actually read what I wrote, I was advocating the
replacement of bit permutations by *different mechanisms for
diffusion*, such as MDS codes, in new designs, rather than the
ridiculous idea of removing essential diffusion steps ciphers
altogether.
> p.s.: The reference is "Differential Cryptanalysis of the
> Data Encryption Standard" by Eli Biham & Adi Shamir.
Sadly out of print now.
[Thanks to Tom St Denis. C-Perm is very similar to his TC1, although
its S-boxes weren't actually `ideal'.]
-- [mdw]
------------------------------
From: "Yo" <[EMAIL PROTECTED]>
Subject: RE: Signed Data
Date: Thu, 20 Jul 2000 12:47:07 +0200
No
Kevin Crosbie <[EMAIL PROTECTED]> escribi� en el mensaje de noticias
8l4uj4$[EMAIL PROTECTED]
>
> Does IE have a scripting function(VBScript, JScript....) which provides
the
> same function as crypto.signText?
>
>
------------------------------
Crossposted-To: talk.politics.crypto,sci.answers,news.answers,talk.answers
Subject: Cryptography FAQ (01/10: Overview)
From: [EMAIL PROTECTED]
Reply-To: [EMAIL PROTECTED]
Date: 20 Jul 2000 11:08:41 GMT
Archive-name: cryptography-faq/part01
Last-modified: 1999/06/27
This is the first of ten parts of the sci.crypt FAQ. The parts are
mostly independent, but you should read this 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.
Disclaimer: This document is the product of the Crypt Cabal, a secret
society which serves the National Secu---uh, no. Seriously, we're the
good guys, and we've done what we can to ensure the completeness and
accuracy of this document, but in a field of military and commercial
importance like cryptography you have to expect that some people and
organizations consider their interests more important than open
scientific discussion. Trust only what you can verify firsthand.
And don't sue us.
Many people have contributed to this FAQ. In alphabetical order:
Eric Bach, Steve Bellovin, Dan Bernstein, Nelson Bolyard, Carl Ellison,
Jim Gillogly, Mike Gleason, Doug Gwyn, Luke O'Connor, Tony Patti,
William Setzer. We apologize for any omissions.
Archives: sci.crypt has been archived since October 1991 on
ripem.msu.edu, though these archives are available only to U.S. and
Canadian users. Another site is rpub.cl.msu.edu in /pub/crypt/sci.crypt/
from Jan 1992.
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.
The fields `Last-modified' and `Version' at the top of each part track
revisions.
1999: There is a project underway to reorganize, expand, and update the
sci.crypt FAQ, pending the resolution of some minor legal issues. The
new FAQ will have two pieces. The first piece will be a series of web
pages. The second piece will be a short posting, focusing on the
questions that really are frequently asked.
In the meantime, if you need to know something that isn't covered in the
current FAQ, you can probably find it starting from Ron Rivest's links
at <http://theory.lcs.mit.edu/~rivest/crypto-security.html>.
If you have comments on the current FAQ, please post them to sci.crypt
under the subject line Crypt FAQ Comments. (The crypt-comments email
address is out of date.)
Table of Contents
=================
1. Overview
2. Net Etiquette
2.1. What groups are around? What's a FAQ? Who am I? Why am I here?
2.2. Do political discussions belong in sci.crypt?
2.3. How do I present a new encryption scheme in sci.crypt?
3. Basic Cryptology
3.1. What is cryptology? Cryptography? Plaintext? Ciphertext? Encryption? Key?
3.2. What references can I start with to learn cryptology?
3.3. How does one go about cryptanalysis?
3.4. What is a brute-force search and what is its cryptographic relevance?
3.5. What are some properties satisfied by every strong cryptosystem?
3.6. If a cryptosystem is theoretically unbreakable, then is it
guaranteed analysis-proof in practice?
3.7. Why are many people still using cryptosystems that are
relatively easy to break?
3.8. What are the basic types of cryptanalytic `attacks'?
4. Mathematical Cryptology
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?
5. Product Ciphers
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, and OFB encryption?
6. Public-Key Cryptography
6.1. What is public-key cryptography?
6.2. How does public-key cryptography solve cryptography's Catch-22?
6.3. What is the role of the `trapdoor function' in public key schemes?
6.4. What is the role of the `session key' in public key schemes?
6.5. What's RSA?
6.6. Is RSA secure?
6.7. What's the difference between the RSA and Diffie-Hellman schemes?
6.8. What is `authentication' and the `key distribution problem'?
6.9. How fast can people factor numbers?
6.10. What about other public-key cryptosystems?
6.11. What is the `RSA Factoring Challenge?'
7. Digital Signatures
7.1. What is a one-way hash function?
7.2. What is the difference between public, private, secret, shared, etc.?
7.3. What are MD4 and MD5?
7.4. What is Snefru?
8. Technical Miscellany
8.1. How do I recover from lost passwords in WordPerfect?
8.2. How do I break a Vigenere (repeated-key) cipher?
8.3. How do I send encrypted mail under UNIX? [PGP, RIPEM, PEM, ...]
8.4. Is the UNIX crypt command secure?
8.5. How do I use compression with encryption?
8.6. Is there an unbreakable cipher?
8.7. What does ``random'' mean in cryptography?
8.8. What is the unicity point (a.k.a. unicity distance)?
8.9. What is key management and why is it important?
8.10. Can I use pseudo-random or chaotic numbers as a key stream?
8.11. What is the correct frequency list for English letters?
8.12. What is the Enigma?
8.13. How do I shuffle cards?
8.14. Can I foil S/W pirates by encrypting my CD-ROM?
8.15. Can you do automatic cryptanalysis of simple ciphers?
8.16. What is the coding system used by VCR+?
9. Other Miscellany
9.1. What is the National Security Agency (NSA)?
9.2. What are the US export regulations?
9.3. What is TEMPEST?
9.4. What are the Beale Ciphers, and are they a hoax?
9.5. What is the American Cryptogram Association, and how do I get in touch?
9.6. Is RSA patented?
9.7. What about the Voynich manuscript?
10. References
10.1. Books on history and classical methods
10.2. Books on modern methods
10.3. Survey articles
10.4. Reference articles
10.5. Journals, conference proceedings
10.6. Other
10.7. How may one obtain copies of FIPS and ANSI standards cited herein?
10.8. Electronic sources
10.9. RFCs (available from [FTPRF])
10.10. Related newsgroups
------------------------------
Crossposted-To: talk.politics.crypto,sci.answers,news.answers,talk.answers
Subject: Cryptography FAQ (02/10: Net Etiquette)
From: [EMAIL PROTECTED]
Reply-To: [EMAIL PROTECTED]
Date: 20 Jul 2000 11:08:42 GMT
Archive-name: cryptography-faq/part02
Last-modified: 94/06/13
This is the second 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:
2.1. What groups are around? What's a FAQ? Who am I? Why am I here?
2.2. Do political discussions belong in sci.crypt?
2.3. How do I present a new encryption scheme in sci.crypt?
2.1. What groups are around? What's a FAQ? Who am I? Why am I here?
Read news.announce.newusers and news.answers for a few weeks. Always
make sure to read a newsgroup for some time before you post to it.
You'll be amazed how often the same question can be asked in the same
newsgroup. After a month you'll have a much better sense of what the
readers want to see.
2.2. Do political discussions belong in sci.crypt?
No. In fact some newsgroups (notably misc.legal.computing) were
created exactly so that political questions like ``Should RSA be
patented?'' don't get in the way of technical discussions. Many
sci.crypt readers also read misc.legal.computing, comp.org.eff.talk,
comp.patents, sci.math, comp.compression, talk.politics.crypto,
et al.; for the benefit of people who don't care about those other
topics, try to put your postings in the right group.
Questions about microfilm and smuggling and other non-cryptographic
``spy stuff'' don't belong in sci.crypt either.
2.3. How do I present a new encryption scheme in sci.crypt?
``I just came up with this neat method of encryption. Here's some
ciphertext: FHDSIJOYW^&%$*#@OGBUJHKFSYUIRE. Is it strong?'' Without a
doubt questions like this are the most annoying traffic on sci.crypt.
If you have come up with an encryption scheme, providing some
ciphertext from it is not adequate. Nobody has ever been impressed by
random gibberish. Any new algorithm should be secure even if the
opponent knows the full algorithm (including how any message key is
distributed) and only the private key is kept secret. There are some
systematic and unsystematic ways to take reasonably long ciphertexts
and decrypt them even without prior knowledge of the algorithm, but
this is a time-consuming and possibly fruitless exercise which most
sci.crypt readers won't bother with.
So what do you do if you have a new encryption scheme? First of all,
find out if it's really new. Look through this FAQ for references and
related methods. Familiarize yourself with the literature and the
introductory textbooks.
When you can appreciate how your cryptosystem fits into the world at
large, try to break it yourself! You shouldn't waste the time of tens
of thousands of readers asking a question which you could have easily
answered on your own.
If you really think your system is secure, and you want to get some
reassurance from experts, you might try posting full details of your
system, including working code and a solid theoretical explanation, to
sci.crypt. (Keep in mind that the export of cryptography is regulated
in some areas.)
If you're lucky an expert might take some interest in what you posted.
You can encourage this by offering cash rewards---for instance, noted
cryptographer Ralph Merkle is offering $1000 to anyone who can break
Snefru-4---but there are no guarantees. If you don't have enough
experience, then most likely any experts who look at your system will
be able to find a flaw. If this happens, it's your responsibility to
consider the flaw and learn from it, rather than just add one more
layer of complication and come back for another round.
A different way to get your cryptosystem reviewed is to have the NSA
look at it. A full discussion of this procedure is outside the scope
of this FAQ.
Among professionals, a common rule of thumb is that if you want to
design a cryptosystem, you have to have experience as a cryptanalyst.
------------------------------
** 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 (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
