Cryptography-Digest Digest #315, Volume #14 Tue, 8 May 01 14:13:00 EDT
Contents:
Re: Best encrypting algoritme (SCOTT19U.ZIP_GUY)
Re: Free Triple DES Source code is needed. (Phil Carmody)
Re: A simple encryption algorithm based on OTP (Doug Kuhlman)
Re: ECC question ("Anthony Mulcahy")
Re: 3x4 grid of triangular numbers (Fred W. Helenius)
Re: A Question Regarding Backdoors (Mok-Kong Shen)
Re: Free Triple DES Source code is needed. (Mok-Kong Shen)
Re: Modification of S-Box attack ("Simon Johnson")
Re: A simple encryption algorithm based on OTP ("Mark G Wolf")
Re: Modification of S-Box attack ("Simon Johnson")
Weird Rijndael test vectors wanted (Mark Wooding)
Re: Modification of S-Box attack (David Wagner)
Re: Modification of S-Box attack (David Wagner)
Re: Modification of S-Box attack (Ross Anderson)
Re: Random and not random ("Douglas A. Gwyn")
Re: SRP attack? (Phil MacKenzie)
Re: ECC question (Mike Rosing)
Re: Back to the Drawing Board (John Savard)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Best encrypting algoritme
Date: 8 May 2001 15:00:23 GMT
[EMAIL PROTECTED] (Mark Wooding) wrote in <[EMAIL PROTECTED]>:
>wtshaw <[EMAIL PROTECTED]> wrote:
>
>> When Rijndael is combined with a chaining mode, it is no longer
>> Rijndael. To measure the strength of an algorithm means no window
>> dressing should be fudged into the process.
>
>But we know how to measure the strength of a chaining mode relative to
>the strength of the underlying block cipher. See, for example, `A
>Concrete Security Treatment of Symmetric Encryption: Analysis of the DES
>Modes of Operation', by Bellare, Desay, Jokipii and Rogaway.
Actually we don't even now how to measure the strength of the
underlying algorithm without the chaining.
One can make assumptions about changes in strength but one can
never be sure. In most encryption modes you can undo the chainning
so that you end up with a set of singly encrypted blocks. The number
of such blocks could depend on the type of message being encrypted.
One would want to minimized repeated blocks. With most chainging or
compression before encryption you make the chance of repeated blocks
less. The hope is either you hide the underlying blocks all together
something seldom done. Or you make it so the underlying blocks appear
to be random. Then one hopes that the attacker doesn't use the information
in such a way that a few sets of blocks provide a complete break.
For things like Rijndeal you may only need 256 pairs of plaintext
cipher text blocks to calulate a break. How one calulates is not something
I know how to do. But from the number of unknows it seems quite possible.
Since moslty likely only one such key would map all 256 pairs. again you
may need a few more. As when solving normal algebric equations. N equations
n unknows. IF they are all independent. If not grab a few more. The point
is the infor to break is in a small number of blocks. That is why
if you want to hide the blocks as much as possible.
If I was to use Rijndael and wanted to hide the blocks
using 3AES as means of doing it I would use three passes of BICOM
reversing file before and after middle pass. The ouput would
be bijective "all or nothing encryption". And I don't see
how an attacker can get any input out blocks of data to plug
in to an NSA computer that may spit out the key.
It makes sense to be warry. Assume the NSA can break it,
even it they can't. How can one hide all data pairs so that
a few can't be graped and put in such a machine. They may even
be able to crack it if they can know relationship between the
blocks. Such weak forms of counter modes. In the game of crypto
its always best to assume the enemy is slightly smaerter than
you are.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE "OLD VERSIOM"
http://www.jim.com/jamesd/Kong/scott19u.zip
My website http://members.nbci.com/ecil/index.htm
My crypto code http://radiusnet.net/crypto/archive/scott/
MY Compression Page http://members.nbci.com/ecil/compress.htm
**NOTE FOR EMAIL drop the roman "five" ***
Disclaimer:I am in no way responsible for any of the statements
made in the above text. For all I know I might be drugged or
something..
No I'm not paranoid. You all think I'm paranoid, don't you!
------------------------------
From: Phil Carmody <[EMAIL PROTECTED]>
Subject: Re: Free Triple DES Source code is needed.
Date: Tue, 08 May 2001 15:22:36 GMT
Mark Wooding wrote:
>
> Phil Carmody <[EMAIL PROTECTED]> wrote:
>
> > Show me the programs and code in K&R 2nd Edition that aren't well formed
> > C++ programs or code.
>
> There are programs in K&R second ediiton which aren't even strictly
> conforming C.
That would surprise me, but I'm not saying it's not possible. It may
well depend on which C standard or draft, and which printing of the book
you're refering to.
> > This is _not_ a forum for language-lawyer discussions, but for
> > cryptography. I hope to see you on comp.lang.c++.moderated if you have
> > anything else to say about C++.
>
> So being wrong about things outside of the group's specific subject
> matter is just fine and perfectly all right and in no way indicative of
> sloppy thinking in general. Good-oh.
I just thought Tom's criticism of the use of the expression "C/C++" was
bizarre (the two do have quite a large intersection, and it's perfectly
possible for the original poster to not care which) and certainly didn't
want to see a language advocacy discussion ensue. I use "C/C++" and
"Perl 4/5" on my CV for example, and noone's been confused by the
expressions yet.
Phil
------------------------------
From: Doug Kuhlman <[EMAIL PROTECTED]>
Subject: Re: A simple encryption algorithm based on OTP
Date: Tue, 08 May 2001 10:14:19 -0500
You're proposing
P = P1 || P2 || P3 || ... || Pn
C = C1 || C2 || C3 || ... || Cn
where C1 = P1 ^ K and Ci = Pi ^ P{i-1}
We can easily create a new stream
D = D1 || D2 || D3 || ... || Dn
where Di = Pi ^ K by setting D1 = C1 and Di = Ci ^ D{i-1}.
This is now a Vigenere cipher, which is easily broken using methods in
the public literature.
Doug
"Siva Prasad Gummadi [T]" wrote:
>
> Hi,
>
> Following is a simple algo. based on OTP which occurred to me just
> a while ago.
> Let's suppose we have N bits of plain text. Choose some k-bit
> key.
> This is a secret key and thus needs to be transmitted to the other end
>
> securely. Choose an appropriate value for k, in context of brute force
>
> attacks. Now the procedure is to divide the plain text into blocks of
> each k-bit length and encrypt (XOR) the first block with the key,
> second
> block with the first block of plain text, and simly., every other
> block with
> the previous plain text block.
>
> Since this is basically OTP I think it should be a good algorithm.
> As per
> my observation, these are the issues with the algorithm:
>
> 1. Private Key system , thus lacks some attractive properties of a
> public
> key encryption system
> 2. Since there are no complex operations involved, you can increase
> the key
> size as required to make brute force attacks impractical, but
> you don't need
> such a large key as in case of actual OTP
> 3. It should be easily broken if the same key is used again, as in
> case of OTP.
> But can some one explain how exactly an OTP becomes venerable
> when a
> key is repeated?
>
> Thanks,
> Siva
>
> --
> ************************************************************
>
> Siva Prasad Gummadi
> Motorola India Electronics Ltd.
> No 33A, Ulsoor Road,
> Bangalore - 560042
> Phone No: 5598615-4007
> email id: [EMAIL PROTECTED]
>
> ************************************************************
> [x] General Information
>
> [ ] Motorola Internal Use only
>
> [ ] Motorola Confidential Proprietary
> ************************************************************
>
>
------------------------------
From: "Anthony Mulcahy" <[EMAIL PROTECTED]>
Subject: Re: ECC question
Date: Wed, 9 May 2001 00:19:33 +0900
"Tom St Denis" <[EMAIL PROTECTED]> wrote
> > Since the curves used in ECC are usually of the form
> > y^2 = x^3 + a4x + a6 (over Fp) or
> > y^2 + xy = x^3 + a2x^2 + a6 (over F2m)
> > the equation for -Q reduces to:
> >
> > -Q = (x, -y-x) = (x, y+x)
>
> I started reading the ECC section in Koblitz's book. It's a bit
complicated
> for a light read... I saw he mentions different curves for different chars
> (p=2,3,>3) is that because they wouldn't exist or because they are weak?
I'm not an expert on this, but my understanding is that the general equation
can be reduced to different simpler forms for the characteristic 2, 3 and >3
cases so that is why mathematicians treat them separately. Curves of
characteristic 2 are popular for ECC, because they are easy to implement and
are thought to be secure when m is a prime, while curves of characteristic
p>3 are popular, because they are believed to be secure when p is a large
prime.
> > nP - kP would be equal to the point at infinity if (n-k) is congruent to
0
> > modulo the order of the group of points on the curve (or the order(s) of
> the
> > subgroup(s) containing P). Basically, nP - kP is equal to the point at
> > infinity, if (n-k) is a multiple of the number of points on the curve.
>
> Isn't that similar to factoring i.e x^2 - y^2 = 0 mod N, x-y may be a
factor
> of N?
If you compare it to factoring, I think the equivalent equation would be
something like
x^n / x^k = x ^ (n-k) = 0 mod N
but I don't know if it's helpful to think of it this way.
Anthony Mulcahy
------------------------------
From: Fred W. Helenius <[EMAIL PROTECTED]>
Crossposted-To: rec.puzzles,alt.math.recreational,sci.math
Subject: Re: 3x4 grid of triangular numbers
Date: Tue, 08 May 2001 11:37:48 -0400
Benjamin Goldberg <[EMAIL PROTECTED]> wrote:
>Could someone direct me to Gau�'s proof that any number can be
>decomposed into the sum of 3 triangular numbers?
Section V of his _Disquisitiones Arithmeticae_. The theorem
is stated and proved in article 293, but the proof depends
upon "the preceding theory"; that is, the theory of quadratic
forms that he develops in the preceding 200+ pages.
--
Fred W. Helenius <[EMAIL PROTECTED]>
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: A Question Regarding Backdoors
Date: Tue, 08 May 2001 17:46:13 +0200
Phil Carmody wrote:
>
> Can a sensible amount of nested 'crippled crypto' be used to emulate
> 'strong crypto'?
> e.g. one can turn DES into Triple-DES (though DES isn't exactly
> crippled).
[snip]
I like to mention that this question is (at least in
some sense) related to an issue described by wtshaw,
which rests yet uncommented on. See my follow-up in the
thread 'Cryptanalysis Question: Determing The Algorithm?'
of 07 May 2001 12:25:01 +0200.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Free Triple DES Source code is needed.
Date: Tue, 08 May 2001 17:56:35 +0200
Phil Carmody wrote:
>
> Mark Wooding wrote:
> >
> > Phil Carmody <[EMAIL PROTECTED]> wrote:
> >
> > > Show me the programs and code in K&R 2nd Edition that aren't well formed
> > > C++ programs or code.
> >
> > There are programs in K&R second ediiton which aren't even strictly
> > conforming C.
>
> That would surprise me, but I'm not saying it's not possible. It may
> well depend on which C standard or draft, and which printing of the book
> you're refering to.
Since we are already at this 'derived' topic, I may be
allowed to ask a question about it: Which current C++
compliers are known to be strictly standard conforming?
(My Microsoft Visual C++ compiler, of version 6.0, isn't.)
Thanks.
M. K. Shen
------------------------------
From: "Simon Johnson" <[EMAIL PROTECTED]>
Subject: Re: Modification of S-Box attack
Date: Tue, 8 May 2001 17:10:00 +0100
David Wagner <[EMAIL PROTECTED]> wrote in message
news:9d6m6d$1eh$[EMAIL PROTECTED]...
> Simon Johnson wrote:
> >Because DES's s-box are so small, 6x4, a small change to their structure
> >(say the swapping of two elements of the box) has massive implications to
> >the effectiveness of differential and linear cryptanalysis. Thus, I
propose
> >an aggressive attack (which in practice would probably be delivered by
> >Virus) where one actually swaps two of the elements in the one or more of
> >the DES s-boxes, in a compiled implementation.
>
> If you're able to modify the S-boxes, why not just zero out
> all the entries in the S-boxes? Maybe I don't understand the
> threat model you are considering: If the adversary can modify
> the implementation, why would it be necessary to minimize the
> number of changes to the S-box?
Yes.. I haven't really defined a threat model.. so my attack doesn't make
sense.
In general, getting a piece of malicious code into a system is harder if its
large. Storing a completely new set of s-boxes in the virus code makes it
harder to 'hide' on the system. Swapping two elements of an s-box though
make more practical sense - The code is a lot smaller, so delivery is
easier.
I see your point though: In theory if one can make such a change to the
algorithm, why not make it trivially weak? -- In practice, 'physical'
constraints might prevent the possibility of such a massive change.
Simon.
------------------------------
From: "Mark G Wolf" <[EMAIL PROTECTED]>
Subject: Re: A simple encryption algorithm based on OTP
Date: Tue, 8 May 2001 11:04:03 -0500
What your overlooking is your plaintext, which is "normally" a specific and
therefore repeated pattern. A good way to see the problem is to consider
your plaintext as being "part" of the key. Each successive XOR with a block
of plaintext is the equivalent of reusing your "key".
------------------------------
From: "Simon Johnson" <[EMAIL PROTECTED]>
Subject: Re: Modification of S-Box attack
Date: Tue, 8 May 2001 17:41:37 +0100
Tom St Denis <[EMAIL PROTECTED]> wrote in message
news:RkBJ6.37313$[EMAIL PROTECTED]...
>
> "Simon Johnson" <[EMAIL PROTECTED]> wrote in message
> news:9d60o4$hsb$[EMAIL PROTECTED]...
> > A lot of people use DES and/or its variants... I've not actually checked
> if
> > this would work.. but in theory it should work perfectly.
> >
> > Because DES's s-box are so small, 6x4, a small change to their structure
> > (say the swapping of two elements of the box) has massive implications
to
> > the effectiveness of differential and linear cryptanalysis. Thus, I
> propose
> > an aggressive attack (which in practice would probably be delivered by
> > Virus) where one actually swaps two of the elements in the one or more
of
> > the DES s-boxes, in a compiled implementation.
>
> You will notice the virus unless it takes effect simultaneously.
>
> Also if you simply remove 16 xor's you can break DES way quicker.
>
> Tom
>
There is a method to my madness =)...
The idea behind doing such a subtle change is that it quite hard to detect.
Swapping two entries in an s-box would result in an implementation equal in
size to the original. Plus, the algorithm has to look convincingly random
ruling out the 16 xor's approach =)
Its a very constrained attack... it doesn't actually attack the cipher
really. It attacks the crypto-system surrounding it. Many people do not
actually check their algorithm is in fact the algorithm they think it is
when they encrypt...
I suppose what I'm demonstrating is that authentication of the algorithm is
not difficult or time consuming and would make it harder (especially if code
is signed) to exploit that particular weakness.
Simon.
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Weird Rijndael test vectors wanted
Date: 8 May 2001 16:37:26 GMT
Does anyone have any Rijndael test vectors for Nk = 5 or 7? The
reference implementation doesn't seem to support these, although they're
in the spec (second version). Just one of each would be fine.
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Modification of S-Box attack
Date: 8 May 2001 16:59:12 GMT
Simon Johnson wrote:
>In general, getting a piece of malicious code into a system is harder if its
>large.
1. Zeroing out S-boxes does not require "large" code.
A simple loop to write zero bytes suffices.
2. I don't see why getting a "large" piece of malicious code into
the system should be that much harder than getting a small piece.
The difference seems small enough that you hardly want to rely on
it for security.
Anyway, Scott Fluhrer's post about better ways to Trojan-horse your
crypto---spike the RNG---seems very persuasive.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Modification of S-Box attack
Date: 8 May 2001 17:00:34 GMT
Simon Johnson wrote:
>The idea behind doing such a subtle change is that it quite hard to detect.
I see no reason that it would be harder to detect than a complete
replacement of the S-boxes. Noone is going to look at the S-box
listings from memory by eye; you'll have to compare the S-boxes
against a known-good source, whether you want to detect a small
or a large change.
------------------------------
From: [EMAIL PROTECTED] (Ross Anderson)
Subject: Re: Modification of S-Box attack
Date: 8 May 2001 17:07:00 GMT
In article <9d60o4$hsb$[EMAIL PROTECTED]>,
"Simon Johnson" <[EMAIL PROTECTED]> writes:
>A lot of people use DES and/or its variants... I've not actually checked if
>this would work.. but in theory it should work perfectly.
>
>Because DES's s-box are so small, 6x4, a small change to their structure
>(say the swapping of two elements of the box) has massive implications to
>the effectiveness of differential and linear cryptanalysis. Thus, I propose
>an aggressive attack (which in practice would probably be delivered by
>Virus) where one actually swaps two of the elements in the one or more of
>the DES s-boxes, in a compiled implementation.
Markus Kuhn and I showed how to do this to some smartcard im0plementations
in `Low Cost Attacks on Tamper Resistant Devices'; see
http://www.cl.cam.ac.uk/ftp/users/rja14/tamper2.ps.gz.
There's much more along these lines in my book, Security Engineering; see
http://www.cl.cam.ac.uk/~rja14/book.html
Ross Anderson
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Random and not random
Date: Tue, 8 May 2001 16:54:16 GMT
Matthew Skala wrote:
> I really don't think there is any way around the bad pad "problem", and I
> really believe it's an illusion anyway. The correct response is to deal
> with the human problem that people are afraid of bad pads, not to attempt
> to somehow get rid of bad pads. Or else, sacrifice perfect secrecy. We
> have such good crypto nowadays (unless you believe in David Scott's
> all-powerful NSA computers that can break 128-bit symmetric crypto in
> milliseconds) that we shouldn't need OTPs. People who are doing
> professional espionage and believe that they really do need OTPs, can (I
> hope) be counted on to *be* professionals, and understand that the bad pad
> "problem" is an illusion.
Bad OTPs are *not* an illusion. Under circumstances which I
decline to go into, defective OTP generators have resulted in
the enemy reading the encrypted traffic. For a similar recent
case, check out the TCP ISN security fiasco -- the RFC calls
for randomly generated 31-bit ISNs, but most implementations
have defects that permit spoofing attacks with fair chance of
success.
If the OTPs are carefully generated from a truly random source,
then statistical checking can detect when the process has
likely developed a defect, which does happen in practice.
Such testing should be properly designed, to avoid introducing
undue bias due to filtering out too many accidental patterns
that occur naturally.
A common problem with OTP systems in practice has always been
the (accidental) reuse of key material. OTP systems should be
designed so that key material is physically destroyed as it is
used. For example, paper-tape systems had a splitter knife in
the tape reader so that reading a tape rendered it not further
readable. A CD-ROM implementation should perhaps be a CD-RW
system that removes links to used blocks of key before
sending them to the encryptor. Things can still go wrong, but
at least there would be one layer of protection.
------------------------------
From: Phil MacKenzie <[EMAIL PROTECTED]>
Subject: Re: SRP attack?
Date: Tue, 08 May 2001 13:26:55 -0400
Actually this feature of SRP was also noticed
by Bleichenbacher a couple years ago, but never published.
Of course, as David points out, it's not really a practical attack.
Whether it's a theoretical attack depends on
your adversarial model. According to the model
used to prove the security of PAK in a Eurocrypt 2000 paper
it would be an attack, since that model specifically allows
the adversary only one password guess per
impersonation attempt. According to the model
used to prove the security of AKE in another
Eurocrypt 2000 paper, it would simply add a factor
of 2 to the adversary's advantage.
I don't think this kind of feature is too common
among password authentication protocols, but there
are some new results concerning this that
will be published sometime in the near future
(in other words, whenever the paper gets accepted to some
conference).
-Phil
David Wagner wrote:
>
> Michael Scott wrote:
> >In fact a masquerading server, Stevie, can eliminate two candidate passwords
> >P1 and P2 at once.
>
> My vague sense is that this might actually be fairly common for
> these type of protocols (although I'm not too sure about it).
>
> Anyway, I don't view it as a problem: The main reason to use a
> protocol like SRP is to force a would-be password-guesser to go
> online, so that you can rig the server with a mechanism that locks
> out the attacker after too many failed attempts to log in. The
> attack you described will only be interesting in this setting if
> the server-threshold is between N and N/2, where N is the number
> of guesses needed to find the user's password, and this doesn't
> sound too likely.
------------------------------
From: Mike Rosing <[EMAIL PROTECTED]>
Subject: Re: ECC question
Date: Tue, 08 May 2001 12:37:17 -0500
> I started reading the ECC section in Koblitz's book. It's a bit complicated
> for a light read... I saw he mentions different curves for different chars
> (p=2,3,>3) is that because they wouldn't exist or because they are weak?
It's more complicated than that. There's a thing called the "j-invariant" which
can be computed for every curve. It's got a factor of 12^3 = 2^6*3^3. If you
don't change the form of the curve for characteristics 2 and 3, that'd leave
you a zero j-invariant for all curves ('cause of the mod operation). By changing
the form of the curve, you eliminate the 2's and 3's so you can get back to
a reasonable equation.
Keep reading :-)
Patience, persistence, truth,
Dr. mike
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Back to the Drawing Board
Date: Tue, 08 May 2001 18:10:50 GMT
On Mon, 07 May 2001 23:10:50 +0200, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote, in part:
>Does that have an alternative name in the coding literature
Terms like "3 of 7 code" instead of "3 out of 7 code" may be used, but
that's about it.
John Savard
http://home.ecn.ab.ca/~jsavard/
------------------------------
** 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 by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
