Cryptography-Digest Digest #945, Volume #11 Mon, 5 Jun 00 07:13:00 EDT
Contents:
RC4 and ciphersaber for the clueless newbie. (Guy Macon)
Re: Faster than light Cryptanalysis (Greg)
Re: P=NP and a polynomial to find all primes. (Daniel A. Jimenez)
Re: DVD encryption secure? -- any FAQ on it (Travis Farral)
Re: Cipher design a fading field? (Runu Knips)
Re: Cipher design a fading field? (Mark Wooding)
Re: Multiple exponentiation (Mark Wooding)
Re: Cipher design a fading field? (Runu Knips)
DES -- Annoyed (tomstd)
Re: DES -- Annoyed (Mark Wooding)
Re: Cipher design a fading field? (Runu Knips)
Re: DES -- Annoyed (tomstd)
Re: DES -- Annoyed (=?ISO-8859-1?Q?H=E4m=E4l=E4inen?= Panu)
Re: Cipher design a fading field? (Mark Wooding)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: RC4 and ciphersaber for the clueless newbie.
Date: 05 Jun 2000 05:28:11 EDT
Scott Fluhrer wrote:
>
>tomstd wrote:
>
>> [EMAIL PROTECTED] (Guy Macon) wrote:
>>
>>>Sorry for being a bother, but I am a clueless newbie who has a
>>>special interest in RC4 (the ciphersaber implementation, really)
>>>and the above went over my head. Could someone explain the
>>above in simple terms?
>
>Maybe you want to pick up a copy of Applied Cryptography by Schneier
>(second edition) and look at it -- RC4 might be the simplest
>believed-secure cipher in existence.
I have looked at it. I don't have it in front of me, but I didn't
see anything about s-boxes. Then again, I am not really clear on
the concept of s-boxes, so maybe I misunderstood.
Here is where I am coming from. I am an autodidact who designs
and programs embedded systems. I have created VCRs, aerospace
test fixtures, a DVD-RAM replication line, etc. and I am currently
designing microcontroller-based toys for a major toy manufacturer.
I know *everything* about designing products and writing programs
for them, but am very limited in the areas of math that are often
discussed in this newsgroup. Given my strengths and weaknesses,
I decided to learn cryptography using the following method:
[1] Identify the simplest possible algorithms.
[2] Study them, write programs using them, and experiment with
variations of them.
[3] Read all the Usenet discussions and web pages about them, and
eventually become able to carry on an intelligent conversation
concerning them.
I chose One Time Pad and Ciphersaber as being the two simplest
methods of encrypting data, so those are the ones that I am
studying first. I believe that I understand the strengths and
weaknesses of OTP pretty well, so now I am focusing on ciphersaber,
arcfour and RC4. My next step will probably be whatever looks like
the simplest asymmetric key system.
------------------------------
From: Greg <[EMAIL PROTECTED]>
Subject: Re: Faster than light Cryptanalysis
Date: Mon, 05 Jun 2000 09:17:18 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (S. T. L.) wrote:
> <<I was just reading an article about a scientist that broke the
speed of
> light>>
>
> The article you referenced said:
>
> <<The process, known as tunnelling, has been used to make some of the
most
> sensitive electron microscopes. >>
>
> This is an already-known phenomenon, discussed in Discover magazine.
When a
> wave packet hits a barrier and tunnels through, it is shifted forward
but the
> actual speed of the packet is unaffected. It's a QM "cheat" and GR is
> unaffected, but it may be useful in technology.
So as I understand what you are saying, the energy is transfered in
some way "Faster than light" can travel?
--
There is only one gun law on the books- the second amendment.
The only vote that you waste is the one you never wanted to make.
RICO- we were told it was a necessary surrender of our civil liberties.
Asset Forfeiture- the latest inevitable result of RICO.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Daniel A. Jimenez)
Subject: Re: P=NP and a polynomial to find all primes.
Date: 5 Jun 2000 04:32:38 -0500
In article <[EMAIL PROTECTED]>,
Dido Sevilla <[EMAIL PROTECTED]> wrote:
>As far as I know it has been proven that there exists no polynomial f(n)
>= nth prime number. And also, to the best of my knowledge, factoring is
>not NP-complete, so finding a polynomial algorithm for factoring
>integers would not necessarily prove that P=NP. All the NP-complete
>problems have the property that any one polynomial-time algorithm for
>one can be adapted to any other by a suitable transformation (which may
>not be trivial). For example, the knapsack problem can easily be
>converted into the traveling salesman problem by considering the weights
>in the knapsack to be distances between cities for the traveling
>salesman. It is not clear whether such a transformation between integer
>factorization and some true NP-complete problem such as satisfiability,
>knapsack, or traveling salesman can be formulated; I think it has even
>been proven that such does not exist (correct me if I am wrong).
Ok, you're wrong :-)
Suppose you were to prove that an NP-complete problem couldn't be
converted into some non-trivial NP problem (like factoring). That would
mean that the non-trivial problem weren't NP-complete. All non-trivial
NP problems are NP-complete if P=NP, thus P!=NP. This has never been
proven. There are, IIRC, other results that make it very unlikely that
factoring is NP-complete (e.g. assuming P!=NP and ERH), but none are
conclusive.
>In
>fact, you can think of all algorithms to perform factoring as being O(N)
>algorithms, where N is the size of the number you want to factor!
Hmm, I think you mean where N is the number you want to factor, not
the size (which is proportional to the logarithm of the number, in
a reasonable encoding like binary). On the other hand, if you have an
algorithm for factoring N-bit numbers in O(N) time, I think the readers
of sci.crypt would like to see it.
--
Daniel Jimenez [EMAIL PROTECTED]
"I've so much music in my head" -- Maurice Ravel, shortly before his death.
" " -- John Cage
------------------------------
From: Travis Farral <[EMAIL PROTECTED]>
Subject: Re: DVD encryption secure? -- any FAQ on it
Date: Mon, 05 Jun 2000 04:39:12 -0500
"David A. Wagner" wrote:
> In article <8h9ba6$cds$[EMAIL PROTECTED]>,
> Bryan Olson <[EMAIL PROTECTED]> wrote:
> > What I mean is that having the bunch of bits - the easy part
> > of the copying process - is not sufficient. You have to
> > create media that looks like a legit DVD. It is not the
> > case that if one can read a DVD one can make a (working)
> > bit-for-bit copy.
>
> Sure it is. It may require hardware -- special hardware
> to press a master, etc. -- and it may require money, but
> it's the same process as used to mass-manufacture DVD's
> (and almost the same process as used to mass-manufacture
> or mass-pirate CD's, I'm told). There are no secrets
> involved, no codebreaking required. Bits is bits.
>
> Sure, you can't go to a website and download the software
> to do bit-for-bit copies. It's not a software attack.
> Consequently, we don't expect Joe Sixpack to be doing bit-for-bit
> copies in his basement. But it would be foolish to expect
> that the criminals interested in mass piracy will be stopped
> by the requirements for DVD-pressing equipment.
>
> > But in my
> > many hours if research (=surfing) on the subject, I have not
> > even heard anyone report success in making working
> > bit-for-bit copies of protected DVD's.
>
> Nor would I expect you to have, but I don't think that makes it
> reasonable to conclude that bit-for-bit copying doesn't go on.
<SNIP>
One thing that has been missed so far is the fact that most DVD movies
cost ~$30US while a blank DVD costs ~$50US (to the consumer anyway,
correct me if I'm wrong) so that means that only the DVD mass-production
houses would benefit from DVD piracy (in a bit-for-bit fashion). In
order for a typical consumer to copy a DVD without spending the $$$ on a
DVD writer and blank DVDs, they would have to either copy it directly to
hard drive consuming 4-6 GB of drive space (which again would cost more
than the movie costs in most cases) or decrypt it and compress it with
DiVX compression or some such that will reduce the size (and quality) of
the movie to a more manageable size (600-800 MB in most cases thus
allowing it to fit on CD or two at ~$0.50/ea). This isn't really a
direct copy, but is a more realistic threat of @large piracy of DVD's.
Keep in mind that even with a decent desktop computer, the ripping and
compression process of an entire 2 hour movie can take 14-18 hours which
will certainly discourage many from attempting this - especially with
the loss in quality and loss of ability to play in many set-top DVD
drives (it can be saved in VCD format so those DVD players that can play
VCDs will retain the ability to play these "copied" discs). Note that
this method DOES require actual decryption of the DVD information off
the DVD (via DeCSS or something similar) and a simple bit-for-bit copy
will not work (it requires the data to be decrypted in order to be
recompressed to the smaller size). So this is where circumventing the
DVD encryption comes into play for piracy.
http://www.dvdpiracy.com is where I got most of this information.
Personally, I'm happy with my VCR and renting movies from the local
Blockbuster - I don't even own a DVD... yet :)
-Travis Farral
[EMAIL PROTECTED]
------------------------------
Date: Mon, 05 Jun 2000 11:51:47 +0200
From: Runu Knips <[EMAIL PROTECTED]>
Subject: Re: Cipher design a fading field?
Mark Wooding wrote:
> I also suspect that more attention ought to be focussed on other useful
> primitives. Hash functions, in particular, seem to be lagging behind.
> Ever faster stream ciphers will be useful.
Interesting. May one also submit hash functions to the cipher contest ?
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Cipher design a fading field?
Date: 5 Jun 2000 10:03:14 GMT
Runu Knips <[EMAIL PROTECTED]> wrote:
> Interesting. May one also submit hash functions to the cipher contest ?
The contest rules accept only block ciphers at the moment. I think this
is a bug, but that's the way it is.
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Multiple exponentiation
Date: 5 Jun 2000 10:09:22 GMT
ahbeng <[EMAIL PROTECTED]> wrote:
> Using algorithm 14.88 (pp 618, Handbook of Applied Cryptography), a
> multiple exponentiation of the form a^x b^y can be done in 1.2
> exponentiation instead of 2.
>
> My question is how to do the following?
> a^x, a^x b^y
>
> I been told that it can be done in 1.2 exponentiation instead of 2.2
> exponentiation by deriving a^x from a^x b^y.
You can clearly improve on 2.2 by computing a^x and b^y separately and
multiplying! But I can't see any improvement beyond that.
(This unhelpful message is to show that we're not all just ignoring your
question.)
-- [mdw]
------------------------------
Date: Mon, 05 Jun 2000 12:18:44 +0200
From: Runu Knips <[EMAIL PROTECTED]>
Subject: Re: Cipher design a fading field?
[EMAIL PROTECTED] wrote:
> Given the results of the cipher contest, it appears that designing a
> strong block cipher is quite easy. Some 7 or 8 ciphers remain unattacked
> on the contest site. Even assuming that all of the ciphers have some
> weakness, it seems that finding a -practical- weakness is very difficult.
Yep. Attacking a cipher is not an easy thing.
> That being said, is cipher design an obsolete enterprise? If a group
> of amateurs can design a strong cipher then certainly governments can.
> Since many government ciphers are available, what is the point of
> creating new ones?
(a) Simply fun
(b) Learning better how to design ciphers
(c) Training skills to break ciphers
(d) Being able to experiment in the next to gigantic field of possible
encryption algorithms
Encryption algorithms have the special property that, unlike other
algorithms, while the task of what to do is quite clear, the ways
how to do it are infinite.
> Speed is one good reason. It seems that AES will answer this
> requirement.
AFAIK none of the AES ciphers is fast enough to satisfy every need
of the hardware freaks.
> Why else is a new cipher required? Will AES be the -final- cipher?
Crypto is far from being a dead field. Many of the things discussed
here (differential and linear cryptanalysis etc) are very young.
------------------------------
Subject: DES -- Annoyed
From: tomstd <[EMAIL PROTECTED]>
Date: Mon, 05 Jun 2000 03:31:13 -0700
As part of my 'Tiny Crypt Lib' I am implementing DES (and then
of course 3key 3des) and have possibly the smallest (and
slowest) implementation ever... problem is I can't find test
vectors for DES anywhere!!!
I looked at the FIPS-42 pages ...etc, nothing. I can't believe
they specify DES without test vectors...
Any help?
Tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: DES -- Annoyed
Date: 5 Jun 2000 10:38:10 GMT
tomstd <[EMAIL PROTECTED]> wrote:
> As part of my 'Tiny Crypt Lib' I am implementing DES (and then
> of course 3key 3des) and have possibly the smallest (and
> slowest) implementation ever... problem is I can't find test
> vectors for DES anywhere!!!
>
> I looked at the FIPS-42 pages ...etc, nothing. I can't believe
> they specify DES without test vectors...
# Test vectors for DES
#
# $Id: des,v 1.1 1999/09/03 08:41:14 mdw Exp $
des {
# --- 7-byte keys ---
00451338957377 4e6f772069732074 3fa40e8a984d4815;
b6c74cbf60c1fd 328da675ff5abd2c cd3e9f9b670671d1;
# --- 8-byte keys ---
0123456789abcdef 4e6f772069732074 3fa40e8a984d4815;
0022446688aaccee 4e6f772069732074 3fa40e8a984d4815;
0123456789abcdef 68652074696d6520 6a271787ab8883f9;
0123456789abcdef 666f7220616c6c20 893d51ec4b563b53;
0123456789abcdef 0123456789abcde7 c95744256a5ed31d;
b763d297f70606fb 328da675ff5abd2c cd3e9f9b670671d1;
}
(My implementation understands DES keys squeezed to 7 bytes, with no
parity, and 8-byte keys with the low bit of each byte ignored.)
-- [mdw]
------------------------------
Date: Mon, 05 Jun 2000 12:34:51 +0200
From: Runu Knips <[EMAIL PROTECTED]>
Subject: Re: Cipher design a fading field?
[EMAIL PROTECTED] wrote:
> No one has figured out how to 'crack' the old ones. DES has never been
> cracked in a practical sense. In fact, cryptanalysis has done more to
> prove the strength of DES than to prove the weakness.
Yep, if one 'modernizes' the design of DES (using a 128 bit block,
allowing 128/192/256 bit keys, dropping the bit conversions at start and
end which don't add any security, changing the bit conversions in the
algorithm itself such that they can be performed faster in software),
I think the resulting cipher would be pretty secure again. Its not
even a hard job to do, is it ?
------------------------------
Subject: Re: DES -- Annoyed
From: tomstd <[EMAIL PROTECTED]>
Date: Mon, 05 Jun 2000 03:53:40 -0700
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
(Mark Wooding) wrote:
>tomstd <[EMAIL PROTECTED]> wrote:
>> As part of my 'Tiny Crypt Lib' I am implementing DES (and then
>> of course 3key 3des) and have possibly the smallest (and
>> slowest) implementation ever... problem is I can't find test
>> vectors for DES anywhere!!!
>>
>> I looked at the FIPS-42 pages ...etc, nothing. I can't
believe
>> they specify DES without test vectors...
>
># Test vectors for DES
>#
># $Id: des,v 1.1 1999/09/03 08:41:14 mdw Exp $
>
>des {
> # --- 7-byte keys ---
>
> 00451338957377 4e6f772069732074 3fa40e8a984d4815;
> b6c74cbf60c1fd 328da675ff5abd2c cd3e9f9b670671d1;
>
> # --- 8-byte keys ---
>
> 0123456789abcdef 4e6f772069732074 3fa40e8a984d4815;
> 0022446688aaccee 4e6f772069732074 3fa40e8a984d4815;
> 0123456789abcdef 68652074696d6520 6a271787ab8883f9;
> 0123456789abcdef 666f7220616c6c20 893d51ec4b563b53;
> 0123456789abcdef 0123456789abcde7 c95744256a5ed31d;
> b763d297f70606fb 328da675ff5abd2c cd3e9f9b670671d1;
>}
>
>(My implementation understands DES keys squeezed to 7 bytes,
with no
>parity, and 8-byte keys with the low bit of each byte ignored.)
>
>-- [mdw]
Unfortunately neither of those are true DES implementations.
The initial 64-bit key is permuted (top of p273 of applied
crypto), in this compression-permutation 56 bits are chosen from
the user key.
Tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: =?ISO-8859-1?Q?H=E4m=E4l=E4inen?= Panu <[EMAIL PROTECTED]>
Subject: Re: DES -- Annoyed
Date: 5 Jun 2000 10:55:47 GMT
tomstd <[EMAIL PROTECTED]> wrote:
: As part of my 'Tiny Crypt Lib' I am implementing DES (and then
: of course 3key 3des) and have possibly the smallest (and
: slowest) implementation ever... problem is I can't find test
: vectors for DES anywhere!!!
: I looked at the FIPS-42 pages ...etc, nothing. I can't believe
: they specify DES without test vectors...
: Any help?
: Tom
Check http://ocelot.cat.syr.edu/~tulsi/des/imagefile.
Panu
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Cipher design a fading field?
Date: 5 Jun 2000 11:08:28 GMT
Runu Knips <[EMAIL PROTECTED]> wrote:
> Yep, if one 'modernizes' the design of DES (using a 128 bit block,
> allowing 128/192/256 bit keys, dropping the bit conversions at start
> and end which don't add any security, changing the bit conversions in
> the algorithm itself such that they can be performed faster in
> software), I think the resulting cipher would be pretty secure
> again. Its not even a hard job to do, is it ?
If my memory is working properly, Preneel found that the `useless'
permutations were of cryptographic benefit in CBC mode. I still agree
that we're better off without them.
My feeling is that bit permutations don't offer sufficiently good
diffusion for a modern block cipher. Techniques like MDS matrix
multiplication provide much stronger properties.
It's often useful in analyses of differential and linear attacks to talk
about `active S-boxes'. Instead, let's think for a bit about `active
bits' -- those bits which are different between a pair of chosen
plaintexts. A bit permutation doesn't affect the number of active bits
at all. Hence, a characteristic through a substitution layer with only
one input and output bit will only give one bit active into the next
substitution layer. This can be converted fairly easily into an attack
on the entire cipher.
An n x n word MDS matrix, on the other hand, will ensure that there are
at least n + 1 words active in any characteristic through the matrix
(counting both input and output words). Thus, a 4 x 4 multiply as in
Square or Rijndael guarantees that 5 S-boxes are active in any two-round
characteristic, and (in conjunction with Square's transposition or
Rijndael's ShiftRow) that 25 are active in any four-round
characteristic. Similar things can be said about Twofish, but the
analysis is more complicated because of the PHT and the rotations, and
the fact that Twofish is a Feistel network rather than an SP-network.
I agree that you can specifically optimize S-boxes in ciphers which are
based on bit-permutations. For example, ensuring that an input
difference with low Hamming weight always (or with very high
probability) yields a high-Hamming-weight output difference and /vice
versa/; similarly for linear characteristics. I think it's more trouble
than it's worth, though.
-- [mdw]
------------------------------
** 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
******************************
