Cryptography-Digest Digest #102, Volume #11 Fri, 11 Feb 00 23:13:00 EST
Contents:
Re: Newbie Encrypt question ("Douglas A. Gwyn")
Re: Latin Squares (was Re: Reversibly combining two bytes?) (zapzing)
Re: Do 3 encryptions w/ a 40-bit key = 120 bits? ("Douglas A. Gwyn")
Re: RFC: Reconstruction of XORd data ("Douglas A. Gwyn")
Re: UK publishes 'impossible' decryption law (zapzing)
Re: Bounding (p-1)(q-1) given only knowledge of pq ("Joseph Ashwood")
Re: Bounding (p-1)(q-1) given only knowledge of pq ("Joseph Ashwood")
Re: Newbie Encrypt question ("Joseph Ashwood")
Re: Latin Squares (was Re: Reversibly combining two bytes?) ("r.e.s.")
Re: need help with a basic C++ algorithm ("Douglas A. Gwyn")
Re: Bounding (p-1)(q-1) given only knowledge of pq (David Wagner)
Re: Period of cycles in OFB mode (David Wagner)
Re: Period of cycles in OFB mode (David Wagner)
Re: Twofish vs. Blowfish (David Wagner)
Re: Twofish vs. Blowfish (David Wagner)
Re: permission to do crypto research (Wim Lewis)
Re: Twofish vs. Blowfish (David Wagner)
Re: RFC: Reconstruction of XORd data (David Wagner)
Re: permission to do crypto research (David Wagner)
Re: Period of cycles in OFB mode ("Scott Fluhrer")
Re: Persistent vs Non-Per DH for Voice (David P Jablon)
----------------------------------------------------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Newbie Encrypt question
Date: Sat, 12 Feb 2000 01:46:19 GMT
Jerry Coffin wrote:
> Yes, DES includes both shifting and XORing, but those are NOT the
> primary elements of the security -- though it's somewhat difficult
> to talk about bits and pieces of a cipher and still say anything
> meaningful, I think it's safe to say that one of the single most
> important elements in the security of DES is in the S-boxes.
Indeed, the S-boxes are the only nonlinear components of DES.
The notion (of the original poster, not Jerry) that security
lies in shifting and XORing is analogous to a notion that the
operation of a computer program depends on NANDing. Undoubtedly
there is a lot of NANDing going on at a very low level in the
computer hardware, but it is the way that that activity is
organized and coordinated that actually accomplishes the useful
higher-level functions. If one tried to deal with computing by
exclusively thinking at the lowest (logic-gate) levels, one
would never be able to achieve the higher functions.
------------------------------
From: zapzing <[EMAIL PROTECTED]>
Subject: Re: Latin Squares (was Re: Reversibly combining two bytes?)
Date: Sat, 12 Feb 2000 01:36:12 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> Latin squares are really only useful if the input alphabet and key
> alphabet are the same size. The DES S-boxes don't have the same sizes
> but seem to work OK.
>
>
Well. actually that is true by definition,
since a latin *square* must be square.
But your post gives me an interesting idea.
What if we generalize it to a latin *rectangle*?
For example, the message symbol could be
one eight bit byte, and the encrypting
symbol could be *two* eight bit bytes.
The latin rectangle would be a
256 X 65536 array of bytes,
arrainged so that every column
has one instance of every byte, and
every row has 256 instances of every byte.
OK so maybe that is a bit large for memory,
but you get the idea.
--
Do as thou thinkest best.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Do 3 encryptions w/ a 40-bit key = 120 bits?
Date: Sat, 12 Feb 2000 01:57:05 GMT
Mike Rosing wrote:
> [EMAIL PROTECTED] wrote:
> > Given that 40 bit encryption is considered insecure, what about the
> > scenario if you take a file and use 40-bit encryption to encrypt it
> > 3 times, would that not give it an effective key length of 120
> > bits, and therefore be secure?
> It'll give you 41.5 bits of security.
The notion of "bits of security" is nonsense. If a random key has 40
bits, then the expected number of trial decipherments for success in
a brute-force key search against a single ciphertext is 2^39,
regardless of the complexity of each decipherment.
What gkare suggests can be read as either C = E(E(E(P,K0),K0),K0) or
C = E(E(E(P,K0),K1),K2). Brute-forcing the former is a 40-bit search;
brute-forcing the latter is a 120-bit search. But that is no
guarantee that the latter system requires 2^80 times the resources to
crack, because brute-force key search is not the only way to attack
systems. (Counterexamples are easy to find.)
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: RFC: Reconstruction of XORd data
Date: Sat, 12 Feb 2000 01:59:53 GMT
Mok-Kong Shen wrote:
> One can simply try all possible values of the first byte to decrypt.
That presumes that one has both strings.
The correct answer is that it is secure (under the assumptions)
for *random* plaintext data.
------------------------------
From: zapzing <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto
Subject: Re: UK publishes 'impossible' decryption law
Date: Sat, 12 Feb 2000 01:59:28 GMT
The police could say "prove that this
really is just a bunch of random numbers
you used as an OTP and not another
encrypted file.
Unfortunately, this might be considered
a reasonable request, since it is
possible to re-create a set of
pseudorandom numbers by just
running the algorithm with the same
seed.
Possessing hard random numbers would
be effectively illegal since you can't prove
they are just random numbers.
It could also be risky to keep any sort
of scientific data around if it has more
digits per data point than can reasonably
be justified by the accuracy of the
measurement device.
--
Do as thou thinkest best.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: Bounding (p-1)(q-1) given only knowledge of pq
Date: Fri, 11 Feb 2000 18:04:28 -0000
I have never claimed that it broke RSA, which seem s to be
what people are assuming I said, what I said is that if you
have a proposed d, you can eliminate some of the
possibilities.
The current best statments I have are:
Take the minimum p, count up to a prime k
set the maximum q to pq/k (rounding down)
use k as the min p proceed as before
take the square root of pq
count down to a prime that prime is the max p
min q = pq/(max p)
these bounds are tighter than I stated before, and will
therefore allow for more claimed d to be eliminated.
> What???
> What difference do you see between 2^1024 possibilities
and
> 2^1022 possibilities.
A factor of 4, it was a matter of correctness, not a matter
of improvement.
> What upper bond of pq is so important?
Because pq is almost necesarily below the other limit that
you were using, in some cases this difference can be nearly
an order of magnitude.
> You are search something like 2^(1024 + X), 0<= X <= 4
for
> your pleasure, values, why not just try to factor.
Actually I am not searching. That is the entire point, using
this method it is possible to eliminate a large portion of
the otherwise possible d, in a relatively short amount of
time. The point is to be able to eliminate values from a
list of potential d.
Joe
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: Bounding (p-1)(q-1) given only knowledge of pq
Date: Fri, 11 Feb 2000 18:04:37 -0000
I have NEVER claimed that this broke RSA, what I have
claimed is that if there is a claimed d it can possibly be
certified as incorrect without encrypting. This is of great
value in some instances, and of none in other instances. I
have also never stated that I knew a way to achieve an exact
(p-1)(q-1) what I did was places further bounds on it.
As to why not factor. Because for 1024 bits that takes too
many resources.
> Note that finding (p-1)(q-1) is provably equivalent in
difficulty
> to factoring pq. So, although it is possible to put
(rather loose)
> bounds on (p-1)(q-1), this doesn't help to break RSA.
Yes, the bounds are quite loose, but they are significantly
small than the generic bands of between 0 and pq.
Joe
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: Newbie Encrypt question
Date: Fri, 11 Feb 2000 18:11:22 -0000
> p.s. I've been told that RC5 is crackable, but for my
purposes I think
> it would work fine.
It actually depends on what you mean by cracked. if you mean
search every possible key until it decrypts to something
meaningful, then yes is can be cracked, of course so can
everyting else. If you mean that a method of breaking the
encryption exists that is significantly better than brute
force, I'd say that you were told wrong. If you mean that if
it's used to protect a program and the program has to
decrypt the itself before it can execute, then I'd say that
you are right, again as with every other encryption scheme.
RC5 is quite secure.
Joe
------------------------------
From: "r.e.s." <[EMAIL PROTECTED]>
Subject: Re: Latin Squares (was Re: Reversibly combining two bytes?)
Date: Fri, 11 Feb 2000 18:21:58 -0800
"Terry Ritter" <[EMAIL PROTECTED]> wrote ...
[...]
: My main reason for using combiners is to complicate or eliminate
: known-plaintext or defined-plaintext attacks. Normally, in a stream
: cipher using an additive combiner, known-plaintext (or just "guessed
: plaintext") will immediately reveal the keystream or confusion stream.
: Then the opponents start to work on the key generator. A keyed
: nonlinear combiner at least prevents easy access.
:
: The reason for having *Latin square* combiners is to prevent leakage
: through either input port. We certainly don't want leakage from
: plaintext. But if we choose things at random I think it would be
: common to find some amount of correlation between output and key under
: known-plaintext conditions. Then the opponents can at least start to
: work on the key generator.
[...]
Additive combiners (XOR or modular addition) are, of course,
a subset of Latin Square combiners. I've looked at your
on-line Glossary to see what you mean by "nonlinear combiner",
but the definition of "linear" is not really clear to me in
this context. The confusion is surely mine, but I have trouble
interpreting the above paragraphs because I'm not sure where
you draw the line between linear & nonlinear combiners. E.g.,
do you consider all Latin Square combiners to be linear?
--
r.e.s.
[EMAIL PROTECTED]
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: need help with a basic C++ algorithm
Date: Sat, 12 Feb 2000 02:35:12 GMT
[EMAIL PROTECTED] wrote:
> What is Rot-47 or Rot-13 or Rot-5. How does it work?
The standard one is "rot-13"; that's short for "rotate the alphabet
(considered as cyclic) 13 positions", i.e. A->N, B->O, C->P, etc.
(Non-alphabetic characters are copied unchanged.) Applying the
rot-13 transformation again to a ciphertext that was produced by
rot-13ing some plaintext will reproduce the original plaintext
(because rotating a 26-character alphabet cyclically 13+13=26 places
gets it back to its original alignment.) Some e-mail user interfaces
support rot-13. Note that this form of encryption is about the
weakest possible, and should not be considered to offer any security.
Rot-47 or rot-5 for 94- or 10-character sets (printable-ASCII or 0..9)
would of course be analogous to rot-13 for the 26-character set A..Z.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Bounding (p-1)(q-1) given only knowledge of pq
Date: 11 Feb 2000 19:11:52 -0800
In article <ehCyq3Pd$GA.174@cpmsnbbsa03>,
Joseph Ashwood <[EMAIL PROTECTED]> wrote:
> I have NEVER claimed that this broke RSA, what I have
> claimed is that if there is a claimed d it can possibly be
> certified as incorrect without encrypting. This is of great
> value in some instances, and of none in other instances.
Can you mention one?
I can't think of any where simply checking the candidate d the obvious
way against an encrypted message wouldn't be better.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Period of cycles in OFB mode
Date: 11 Feb 2000 19:17:02 -0800
In article <[EMAIL PROTECTED]>,
John Savard <[EMAIL PROTECTED]> wrote:
> However, I would have thought the
> Birthday Paradox would make it even lower than 2^(m-1).
Nope. The Birthday Paradox doesn't apply here.
(It would only apply if DES were a pseudorandom function; but DES
has extra structure -- it is a permutation (bijective).)
If we replace DES with a permutation chosen uniformly at random,
there are classical results which say the average cycle length (if you
start at a random place) is -- if I remember correctly -- (2^n + 1)/2;
moreover, the cycle length is uniformly distributed, i.e., the chances
of seeing a cycle of length j, for 1<=j<=2^n, is exactly 1/2^n.
See Knuth for details.
This is all from memory, so take it with a grain of salt, but I think
it's roughly right.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Period of cycles in OFB mode
Date: 11 Feb 2000 19:18:37 -0800
In article <[EMAIL PROTECTED]>,
Paul Koning <[EMAIL PROTECTED]> wrote:
> That's why I've always liked counter mode. Its cycle size is
> obvious (2^64).
But it is worth mentioning that counter mode also starts to exhibit
some regularities (a birthday paradox-like issue) after about 2^32 blocks,
so it would only be prudent to change keys well before that point.
(I'm assuming you're using a block cipher with 64-bit block size.)
> It also has the nice property that you can
> parallelize it for higher speed.
Yup. From my point of view, this is the big win of counter mode.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Twofish vs. Blowfish
Date: 11 Feb 2000 19:21:59 -0800
In article <[EMAIL PROTECTED]>, John Myre <[EMAIL PROTECTED]> wrote:
> I'd start with RC6 (another of the AES candidates), because it is by
> far the easiest to code, which means it is the easiest to get right.
Yeah, it is, but there's not much reason to implement any of the free AES
candidates yourself -- you can readily get free implementations of, e.g.,
Twofish, if you like. I'm pretty sure you can also easily find free
implementations of Rijndael and Serpent as well, but I haven't looked closely.
The downside of using RC6 right away is that -- as far as I know -- it isn't
free yet (patents), and may not be unless it ends up winning.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Twofish vs. Blowfish
Date: 11 Feb 2000 19:23:24 -0800
In article <[EMAIL PROTECTED]>, John Myre <[EMAIL PROTECTED]> wrote:
> AFAIK, patents
> are only relevant once you start to sell it (or the equivalent).
That turns out not to be the case.
Using a patented algorithm, even for research purposes only, is illegal.
Whether or not you sell it is irrelevant.
------------------------------
From: [EMAIL PROTECTED] (Wim Lewis)
Crossposted-To: talk.politics.crypto,misc.int-property,misc.legal.computing
Subject: Re: permission to do crypto research
Date: 12 Feb 2000 03:28:39 GMT
In article <87npgt$5pa$[EMAIL PROTECTED]>,
Mike Eisler <[EMAIL PROTECTED]> wrote:
>While I'm this thread, I'm having a lot of trouble understanding
>somewthing. I've read the NY court decision granting the injunction.
>The judge seems to be equating the DeCSS code with a way to break copy
>protection.
>
>However, as far as I can tell, all that code does is allow one to view
>the encrypted contents. If it were impossible to read the contents of
>the DVD (think back to early days of cdrom controllers that had
>firmware that prevented CD track reading .. this doesn't appear to be
>the case for DVD), then the DeCSS code would be useless. What is to
>prevent one from taking a DVD and copying the encrypted contents onto
>another (writable) DVD?
I, too, was confused by this for a while. But apparently the encryption
is useful for preventing copying. The DVD drive will refuse to read certain
parts of the disk unless it has "authenticated" the computer. This is a
cryptographic exchange which sets up a "bus key" which encrypts the
communication between the drive and the DVD-video decoder. The idea is
apparently that both the DVD drive and the video-decoder are tamper-resistant
hardware modules whose manufacture can be controlled by the DVD consortium.
Originally, as I understand it, the consortium did not want to allow
software decoders, or even hardware decoders which didn't talk directly
to the video card through some proprietary channel, to make it harder to
duplicate a disk. DeCSS has code both for unencrypting the .vobs and for
performing the authentication step to get the drive to read the protected
sectors.
Disclaimer: the above has been gleaned from various sources, and may not
be perfectly accurate ...
(Another point is that the encryption is used for "region coding" of DVDs,
which is AFAICT a gratuitous attempt to preserve the market segmentation
caused by different worldwide video standards. DeCSS *does* bypass the
region restriction, which may also make video distributors unhappy.)
--
Wim Lewis * [EMAIL PROTECTED] * Seattle, WA, USA
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Twofish vs. Blowfish
Date: 11 Feb 2000 19:28:18 -0800
In article <[EMAIL PROTECTED]>, John Myre <[EMAIL PROTECTED]> wrote:
> Actually I suppose that you could get the same sort of developmental
> behavior by using an "encryption algorithm" that you make up yourself
> and is trivial. It doesn't have to be secure; it just has to have
> the right interface and scramble the data at least a little, so as
> to support testing.
>From a software-engineering point of view, this is pretty scary advice.
The lesson of the Kerberos -- and Netscape -- key generators is that
you *will* forget and leave it in your published product once, and if
you're particularly unlucky, noone may realize it for years.
(In case you hadn't heard of the Kerberos case, they initially put in
a really insecure key-generator just to get things working. They knew
it was bogus and had intended to replace it. Indeed, they even did replace
it in one code base. But somehow the patch that installed the secure
key-generator got lost or overlooked somehow in the shuffle, and so it
turned out that Kerberos had been using the insecure key-generator for
years. It was only discovered after flaws were found in the Netscape
key-generator and someone thought to check out Kerberos to see if it was
safe. And that was before the time pressures of "Internet time"!)
I often find the creative ways that Murphy's Law finds to bite you in
the butt quite awe-inspiring. Why take chances?
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: RFC: Reconstruction of XORd data
Date: 11 Feb 2000 19:31:22 -0800
In article <[EMAIL PROTECTED]>,
Ian Clarke <[EMAIL PROTECTED]> wrote:
> In theory, each of these strings is more-or-less useless for
> reconstructing the data without the other (unless the data is extremely
> predictable, much more so than English text).
Actually, in theory, either of these strings alone is likely to be
enough to recover all, or most, of the original English text.
Experiments show that English has only a few bits of entropy per
character (the figure I remember is 2 bits, but I could be misremembering).
Consequently, speaking from a purely information-theoretic perspective,
one would expect that either of those strings is more than enough to
reconstruct the plaintext.
Frankly, I'd advise you to re-think your proposed algorithm, and even
more important, to think carefully about what purpose it is intended to
serve. (What's your threat model? What are you trying to protect? etc.)
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Crossposted-To: talk.politics.crypto,misc.int-property,misc.legal.computing
Subject: Re: permission to do crypto research
Date: 11 Feb 2000 19:40:07 -0800
In article <882k17$s6l$[EMAIL PROTECTED]>,
Wim Lewis <[EMAIL PROTECTED]> wrote:
> I, too, was confused by this for a while. But apparently the encryption
> is useful for preventing copying. The DVD drive will refuse to read certain
> parts of the disk unless it has "authenticated" the computer. [...]
But code to break this part of the security architecture was available for
a long time before DeCSS came out. The novel feature of DeCSS was that it
also broke CSS, the encryption algorithm.
If it really were the "authentication" the DVD industry was worried about,
then their current legal strategy would count as poorly-thought out, at best:
banning DeCSS won't get rid of the existing information and tools for breaking
the "authentication" step. But I don't think it's the "authentication" they
are so concerned with protecting. And indeed, a perusal of the DVD industry
court briefs suggest that it is the crack of the CSS encryption algorithm, not
the "authentication" crack, that they are up in arms about -- they specifically
mention CSS by name a number of times, but don't mention "authentication" as
far as I can see.
So, it's not the "authentication". Back to the drawing board (or to confusion).
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: Period of cycles in OFB mode
Date: Fri, 11 Feb 2000 19:37:19 -0800
Paul Koning <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Scott Fluhrer wrote:
> >
> > Tim Tyler <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> > > It appears to me that when using most block cyphers in OFB mode, there
> > > will exist both weak keys (keys where there exists no period anywhere
> > > near 2^n in length), and - for the vast mayority of keys - there
> > > will be weak IVs (IVs that happen to hit on a shorter-than normal
> > > cycle).
> > >
> > > I am interested to learn about what efforts (if any) have been made
> > > to avoid these problems in block cyphers in OFB mode.
> > Well, one obvious approach would be to add in a step counter after every
> > encryption step. That is, (if X(n) is the internal state at step n),
turn:
> >
> > X(n+1) = Encrypt( X(n) )
> >
> > into
> >
> > X(n+1) = Encrypt( X(n) ) + n
> >
> > where the above + is either xor, or addition modulo the block size.
> > Then, cycles are impossible (if X(n) = X(m) for some n!=m, then
> > X(n+1) != X(m+1) )
[nb: assuming, as others have pointed out, that you don't overflow the
counter]
>
> Of course that's not true.
>
> In OFB, you have a cycle of length k if E(X(k-1)) == X(0).
>
> In your scheme, you have a cycle of length k if E(X(k-1)) + n == X(0).
Err, no, that's not a cycle. A cycle of length k happens iff, for all n
X(n) == X(n+k)
However, if X(k) == X(0), or E(X(k-1)) + k-1 == X(k) == X(0), then
X(k+1) == E(X(k)) + k == E(X(0)) + k != E(X(0)) + 0 == X(1)
--
poncho
------------------------------
From: [EMAIL PROTECTED] (David P Jablon)
Subject: Re: Persistent vs Non-Per DH for Voice
Date: Sat, 12 Feb 2000 03:52:46 GMT
If you're looking for ways to authenticate static and ephemeral
DH exchanges, don't forget to look at how it can be done with
a small shared secret, like SPEKE, SRP, or EKE.
See www.IntegritySciences.com for details.
In article <[EMAIL PROTECTED]> Mike Rosing wrote:
>[EMAIL PROTECTED] wrote:
>>
>> By session key, you mean the DH ephemeral key which in turn creates a
>> session key using a symetric cipher...
>
>The two DH keys of each side create the session key used with the
>symetric cipher.
>
>> OK...it may be more secure, but what about the setup time each time a
>> call is made...and man in the middle attack...
>
>Problems to deal with for sure!
>
>> Is this techqnique widely used in two way real time communications?
>
>Not widely, but it's used in some secure phones. Doing a MITM with RF
>in real time is pretty hard.
>
>> Any references to the MQV algorithm?...I cant find any papers or source
>> code....if you have any URL, I would be glad to have them...thanks
>
>Check out the P1363 web site at ieee:
>http://grouper.ieee.org/groups/1363/D9.html
>(send me e-mail via [EMAIL PROTECTED] and I'll send you the
>username,password to get the downloads)
>
>> Certicom?
>
>Yup.
>
>Patience, persistence, truth,
>Dr. mike
======================================================
David P. Jablon
Integrity Sciences, Inc.
[EMAIL PROTECTED]
<http://www.IntegritySciences.com>
------------------------------
** 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
******************************
