Cryptography-Digest Digest #996, Volume #11 Sat, 10 Jun 00 13:13:01 EDT
Contents:
Re: How does DES work? (tomstd)
Re: Random sboxes... real info (tomstd)
Re: Cryptographic voting ("Trevor L. Jackson, III")
Re: Cryptographic voting ("Trevor L. Jackson, III")
Re: How does DES work? (John Savard)
Re: Cipher design a fading field? (John Savard)
Twofish Idea (tomstd)
Cryptanalytic gap [was: Re: Some dumb questions] ("Trevor L. Jackson, III")
Re: My lastest paper on Block Ciphers ("Trevor L. Jackson, III")
Re: Cipher design a fading field? (John Savard)
Re: My lastest paper on Block Ciphers (tomstd)
Re: Some dumb questions (Jim Gillogly)
Q: Using two DES modules (Mok-Kong Shen)
Re: Q: Using two DES modules (Mok-Kong Shen)
Re: How does DES work? (Mok-Kong Shen)
Re: Large S-Boxes (David A. Wagner)
Re: Random IV Generation (Terry Ritter)
----------------------------------------------------------------------------
Subject: Re: How does DES work?
From: tomstd <[EMAIL PROTECTED]>
Date: Sat, 10 Jun 2000 05:27:03 -0700
In article <[EMAIL PROTECTED]>, Quisquater
<[EMAIL PROTECTED]> wrote:
>tomstd wrote:
>
>> DES is certainly a dead cipher, but you can find some papers
Eli
>> Biham on DES (he is one of the dudes that broke DES). Also
>> check out FIPS-42 I think... (NIST).
>>
>> Tom
>
>Certainly?
>Can you elaborate, please? I don't agree at all (and
differential
>cryptanalysis found by Eli Biham and Adi Shamir is not breaking
>DES at all). The only weak point (today!) is the key length of
DES.
>Triple DES is a solution (DES-X ?). Do you how many applications
>are using DES today (correctly) and are not broken? DES was in
the
>field from 1975: How many "new" ciphers (IDEA, twofish, ...)
will
>be in the field for the next 25 years (I know I'm provocative
here)?
I meant academically broken, not practically.
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!
------------------------------
Subject: Re: Random sboxes... real info
From: tomstd <[EMAIL PROTECTED]>
Date: Sat, 10 Jun 2000 06:48:13 -0700
Based on my testing of 4x4 sboxes it appears only %0.4 of all
random tested sboxes achieve LPmax=DPmax=4. This is fairly low,
and it's even lower with larger sboxes.
I.e is my point comming through? Random sboxes are hardly ideal.
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!
------------------------------
Date: Sat, 10 Jun 2000 10:07:31 -0400
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: Cryptographic voting
Greg wrote:
> > One of the problems such a system causes is instability.
> > A stable system requires a degree of hysteresis so that
> > small oscillations in voter sentiment do not produce
> > large changes in the government. This is one reason that it
> > takes a higher percentage to remove an official than to elect him.
>
> This can be the case in my hypothetical government structure.
>
> > Another problem with similar systems is that there is no
> > practical limit to the power of the executive. It is much
> > like a monarchy in which everyone knows who is accountable
> > (the king), and what his duties are (to protect the
> > subjects), but there is no mechanism by which a tyrannical
> > king can be removed if he keeps his small constituency
> > (classically the nobles; your senate) happy.
>
> Thus, the one year term for the senators and NO chance they can ever
> return.
>
> >
> > The worst problem with this style of government is that
> > it tends to be a popular democracy. All such systems
> > become oppressive due to "the tyranny of the majority".
>
> That's why the constitution to keep the king in check.
Pieces of paper do not keep rulers in check. Competing powers keeps rulers in
check. Thus the "balance of power" in the US gov't tripod.
> The purpose of
> the "king" factor was to eliminate the blame game. That is what has
> allowed Clinton to mess with America and get away with it. There are
> too many people that like him to the point of blind loyalty - willing
> to believe that the GOP is responsible for everything Clinton has
> failed at.
Clinton isn't the problem, he's a symptom. The problem is the state of the
electorate.
------------------------------
Date: Sat, 10 Jun 2000 10:09:19 -0400
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: Cryptographic voting
Virgil wrote:
> In article <8hq5cu$ceg$[EMAIL PROTECTED]>, Greg <[EMAIL PROTECTED]>
> wrote:
>
> >>
> >> Their leader seems to have given up the role of Moses to take up the
> >> role of Julius Caesar.
> >
> >If the gunners are the government, then I would think that a better
> >description is that their leader seems to have given up the role of
> >Washington for Hitler or Stalin.
>
> That should be your first clue that the "gunners" in the U.S.A. are
> those who put the right to own weapons of distruction before all other
> rights, even the right to life.
How do you distingush the weapons of destruction from the weapons of defense?
Is there a touch of hloplophobia in your position?
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: How does DES work?
Date: Sat, 10 Jun 2000 13:59:15 GMT
On Sat, 10 Jun 2000 09:14:39 GMT, "Michael Brown"
<[EMAIL PROTECTED]> wrote, in part:
>and was wondering if it is something like this: each bit
>specifies a command, for example 0=swap each bit with its neighbour to the
>right, 1=swap each bit with its neighbour to the left, so a 56 bit key
>would have 56 "instructions".
No, it definitely doesn't work like that, although that might well be
an interesting principle for a cipher.
There is a complete description of DES on my web site, and the
standard is also available on the Internet at the NIST web site.
John Savard (teneerf <-)
http://www.ecn.ab.ca/~jsavard/
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Crossposted-To: sci.math
Subject: Re: Cipher design a fading field?
Date: Sat, 10 Jun 2000 14:11:58 GMT
On Tue, 06 Jun 2000 03:11:16 GMT, "Douglas A. Gwyn" <[EMAIL PROTECTED]>
wrote, in part:
>John Savard wrote:
>> But some people have expressed a wish for proofs of security for
>> ciphers, and in my opinion, that looks like something equivalent to
>> solving the halting problem.
>Maybe an attempt to prove that equivalence would prove enlightening.
Well, to see if such an attempt is feasible, let us review what the
halting problem is. It concerns itself with the question:
Is there a finite algorithm, which, when a computer program is
submitted to it, will tell you, in a finite time, whether or not that
program will halt?
One trivial algorithm that comes to mind would just be to take the
computer program, and try running it. Clearly, if the program halts,
it will do so after a finite time (a program that runs forever is one
that does not halt). However, this algorithm by itself does not at any
time distinguish between programs that will never halt, and programs
that simply have not halted _yet_.
This, however, assumes that the time a computer program that will
eventually halt will take to run is unbounded, thus, the term
"computer program" is meant in the abstract, and includes programs of
unbounded size, requiring unbounded amounts of memory.
Obviously, it is possible to tell of some programs that they
definitely will never halt. A program might have a trivial infinite
loop that can be found by inspection. Also, one can run a program, and
check to see if during that execution, the program's state ever
repeats. (A way to do this without requiring prodigious amounts of
memory and enormous searches, incidentally, is to allow two copies of
the program to run at incommensurable speeds, giving the faster one a
head start, and continuously compare their states for equality. The
continued fraction representations of the quadratic irrationalities
are useful in providing a schedule for stepping the copies of the
program.)
Thus, what remains to be seen concerning the halting problem is simply
this: do there exist programs which, although they will never halt,
fail to halt for "nontrivial" reasons: reasons that no finite
algorithm can find?
We now know that a program which searches for a counterexample to
Fermat's Last Theorem will never halt. But such a program would not
fail to halt because it contained a simple infinite loop; it fails to
halt because Fermat's Last Theorem is true, as recently proven by
Andrew Wiles. What about a program that searches for a counterexample
to the Riemann conjecture, or the Goldbach conjecture? What about a
program that searches for an odd perfect number?
A program that could determine whether or not any other program would
halt, therefore, would have the ability to solve any unsolved problem
in mathematics, provided that problem has a solution. This flies in
the face of Goedel's proof that some mathematical questions are
undecidable.
Alan Mathison Turing found direct proof that the halting problem
cannot be fully solved, which I will attempt to present below.
This proof is based on the fact that every computer program is a
finite string of symbols (although of unbounded length: for any
program, one can find a larger, but still finite, one), and from a
finite alphabet (or an alphabet of cardinality aleph-null, but
finiteness can be assumed without loss of generality, since delimited
strings of unbounded length composed of characters from a finite
alphabet can represent the elements of an alphabet with aleph-null
symbols). Hence, any program can be coded so that it can be
represented by some positive integer.
What we desire is a program that states, in some finite time, when
given a program that will not halt that, in fact, this is a program
that never halts. If such a program exists, it could have a
pre-processing step added to it so that it accepted programs as input
for consideration in the form of the positive integer which represents
it.
Also, note that such a program could be incorporated into a program
that spent part of its time running the program that was submitted to
it, so that it would halt and report whether or not the program given
to it as input halted or was proved never to halt. Or, it could be
designed so that if it finished looking for a proof that a program
would never halt, and found none, it would go into an infinite loop
and never halt itself. It is this latter form of the program we are
concerned with.
(As this is a classic proof, if you happen to have read a bit about
modern mathematics, you may well already know what comes next...)
Now, then, we submit to this form of the program the integer that
represents itself.
Actually, this step involves cheating a bit. Here, we have
distinguished between a "program" and its "input", and noted that a
program might halt or not halt, depending on properties of its input.
If so, there won't be a single answer for a great many programs.
Obviously, then, to talk about determining for a number n whether or
not it represents a program that halts, we need to disallow any
additional input.
This is simple enough to do: programs requiring input would then be
represented by many different programs: for each possible input, there
would be a version which began with a program to write that sequence
of input in an area of memory, and then runs a version of the original
program that reads its input from that area of memory.
A program that takes its entire text as input is possible, since the
storage containing the program itself can be read and copied
somewhere.
But what you now have is a program that will halt if and only if it
does not halt. Given n as input, it halts if program n does not halt,
and goes into an infinite loop if n does not halt. But it _is_ program
n. Since having a program that tells us when programs don't halt
allows us, through trivial transformations we know are possible, to
create this impossible program, we can't possibly have such a program.
Since this proof depends on our ability to determine the status of
_any_ program, if we restrict ourselves to just one narrow kind of
program, the proof may not apply. The question that would need to be
decided here is: is trying to find a way to crack a cipher a very
narrow subset of mathematics, or is it open-ended enough that one
could, for just about any mathematical conjecture, design a cipher
such that finding a solution to that cipher, or proving one did not
exist, was equivalent to finding a counterexample, or proving, the
conjecture? That is a difficult question: how would one design, for
example, a cipher that was secure if and only if Goldbach's Conjecture
is true? On the other hand, cipher design does seem to be fairly
open-ended.
John Savard (teneerf <-)
http://www.ecn.ab.ca/~jsavard/
------------------------------
Subject: Twofish Idea
From: tomstd <[EMAIL PROTECTED]>
Date: Sat, 10 Jun 2000 07:23:22 -0700
Twofish is a Balanced Feistel Network where the 'F' function
takes 64 bits in, and produces 64 bits out. One 'flaw' I see is
in the 'g' functions. The F function begins with two
applications of the 'g' function which is a permutation of the
32 bit input. I.e it resembles..
a --> g(A) ---> P
H ---> 64-bit Output
b --> g'(B) --> T
g' is similar to g except it rotates the input byte 8 bits to
start with. The above digram should have the three letter
word 'PHT' aligned vertically (to look proper). If it didn't
come out this way... please just reedit it.
The 'g' function itself is just
g(a) --> mds(a) --> bytesub(a) -->
Where mds() and bytesub() are the same for either g or g'. The
purpose of the mds is to linearly (in GF(2)) mix the 4 byte
input vector so that there is a high avalanche.
However I don't think the data path is entirely optimal because
the 64-bit input is split into two halves the diffusion is at
most on one half of the input. If for example it achieves ideal
diffusion in 'g' then only 16 of the 64 output bits will flip on
average, not 32. Even through the PHT which should make the
figure closer to 32 the bits that flip will be related in
position.
Ideally they should have used a 8x8 MDS and 8 unique sboxes.
This could be precomputed as eight 8x64 sboxes and xor them
together. This would increase the memory and execution time,
but have a more ideal data path.
This is purely speculative, just my two cents worth.
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!
------------------------------
Date: Sat, 10 Jun 2000 10:47:44 -0400
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Cryptanalytic gap [was: Re: Some dumb questions]
Jim Gillogly wrote:
> The "dead system" is the N-time pad, not the 1-time pad.
This is a succinct summary of the issues of the original thread, but it
sparked my awareness of a gap in the literature (more probably a gap in my
knowledge or understanding of the literature) regarding key usage. On one
hand we have the OTP model and on the other we have PK and SK systems. OTPs
rely upon the quality and quantity of the key and its unique usage for
strength. PK and SK systems rely upon the transforms applied to the key and
text for their strength, allowing exponentially large key reuse (like reuse <
2^(keylength/2))
This leaves a gap in the frequency of key use. Is there a kind of
cryptographic system in which re-using a key is acceptable up to some small
limit (1 < limit <= polynomial(leylength))?
------------------------------
Date: Sat, 10 Jun 2000 11:01:21 -0400
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: My lastest paper on Block Ciphers
tomstd wrote:
> I will try to use the latex tools in the future.
Careful Tom, if you start using professional tools it will become difficult to
claim that crypto is only a hobby. ;-)
Note also that it is good practice to reserve presentation tools for polished
products. Something you scribbled on a napkin while eating lunch should be
presented on the original napkin, not on a bonded, watermarked paper. The rule
is that fuzzy ideas should look fuzzy and carefully thought out ideas should
look professional.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Crossposted-To: sci.math
Subject: Re: Cipher design a fading field?
Date: Sat, 10 Jun 2000 14:42:37 GMT
On Sat, 10 Jun 2000 14:11:58 GMT, [EMAIL PROTECTED]
(John Savard) wrote, in part:
>(A way to do this without requiring prodigious amounts of
>memory and enormous searches, incidentally, is to allow two copies of
>the program to run at incommensurable speeds, giving the faster one a
>head start, and continuously compare their states for equality. The
>continued fraction representations of the quadratic irrationalities
>are useful in providing a schedule for stepping the copies of the
>program.)
Actually, comparing the states of two programs with every possible
relative time delay doesn't require the use of an irrational number as
the speed ratio.
John Savard (teneerf <-)
http://www.ecn.ab.ca/~jsavard/
------------------------------
Subject: Re: My lastest paper on Block Ciphers
From: tomstd <[EMAIL PROTECTED]>
Date: Sat, 10 Jun 2000 07:49:42 -0700
In article <[EMAIL PROTECTED]>, "Trevor L. Jackson,
III" <[EMAIL PROTECTED]> wrote:
>tomstd wrote:
>
>> I will try to use the latex tools in the future.
>
>Careful Tom, if you start using professional tools it will
become difficult to
>claim that crypto is only a hobby. ;-)
>
>Note also that it is good practice to reserve presentation
tools for polished
>products. Something you scribbled on a napkin while eating
lunch should be
>presented on the original napkin, not on a bonded, watermarked
paper. The rule
>is that fuzzy ideas should look fuzzy and carefully thought out
ideas should
>look professional.
Well I doubt anyone in their right mind would publish my papers,
so I will resort to PS copies only for now.
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: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: Some dumb questions
Date: Sat, 10 Jun 2000 15:15:11 +0000
Guy Macon wrote:
>
> Jim Gillogly wrote:
>
> >The "dead system" is the N-time pad, not the 1-time pad.
>
> Substituting characters from a random table in the form "A=Q, B=H, C=N..."
> is dead too, but learning WHY it's dead is a great way of starting out
> on the path of learning cryptanalysis. If I want to learn more about
> cracking N-time pads and someone is willing to teach me, you are wrong
> to discourage such on-topic behaviour.
Point taken. Knock yourself out, big guy. If you're not satisfied with
the volume of the current thread, you'll find most of the points raised
in it repeated numerous times in DejaNews and in the hard-copy literature.
--
Jim Gillogly
Trewesday, 21 Forelithe S.R. 2000, 15:12
12.19.7.5.1, 1 Imix 4 Zotz, Second Lord of Night
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Q: Using two DES modules
Date: Sat, 10 Jun 2000 18:20:17 +0200
Given two two DES modules and two keys, which of the following
schemes is to be preferred, (a) in ECB and (b) in CFB?
1. Superencipherment (2DES).
2. Use one DES in full OFB for preprocessing the plaintext
with xor before input to the other DES.
3. Use one DES in full OFB to generate keys for the other
DES.
Note that (3) needs only one key. Does the comparison gets
changed, if the two keys of (1) or (2) are identical?
Intuitively, I think that (3) could be superior.
Many thanks in advance.
M. K. Shen
============================
http://home.t-online.de/home/mok-kong.shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Q: Using two DES modules
Date: Sat, 10 Jun 2000 18:23:59 +0200
Mok-Kong Shen wrote:
> Given two two DES modules and two keys, which of the following
Sorry, should read 'Given two DES modules ....'
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: How does DES work?
Date: Sat, 10 Jun 2000 18:36:50 +0200
Michael Brown wrote:
> Any pointers to DES info also appreciated.
D. R. Stinson, Cryptography. CRC, 1995.
C. F. Meyer, S. M. Matyas, Cryptography. Wiley, 1982.
H. Katzan, The standard data encryption algorithm. PBI, 1977.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: Large S-Boxes
Date: 10 Jun 2000 09:38:13 -0700
There's nothing wrong with wanting to study cipher design. I think it
is a very fun and rewarding field! But don't expect to find a ``dummy's
guide'' that lets you avoid the hard work; you'll probably need to slog
through the literature and practice, practice, practice if you want to
learn the material.
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Random IV Generation
Date: Sat, 10 Jun 2000 16:57:53 GMT
On Sat, 10 Jun 2000 13:05:21 +0200, in
<[EMAIL PROTECTED]>, in sci.crypt Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
>Terry Ritter wrote:
>
>> Counter mode with a binary counter seems to be just asking for
>> trouble. One alternative would be to use a polynomial counter, to get
>> about half the "counting" bits to change on each count, which should
>> be a lot less risky.
>
>Sorry for my ignorance. What is the definition of a polynomial counter?
>Thanks.
Instead of counting in binary sequence, use a finite field.
Typically, this would be a simple linear feedback shift register
(lfsr). There is no strength required for the counting sequence; the
strength improvement comes from not presenting a sequence in which
only one bit changes fully half the time.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
** 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
******************************
