Cryptography-Digest Digest #317, Volume #14 Tue, 8 May 01 19:13:01 EDT
Contents:
Re: ISO 9796-1:1991 (Uwe Guenther)
Re: Best, Strongest Algorithm ("Douglas A. Gwyn")
Re: RSA BRUTE FORCE ("Douglas A. Gwyn")
Re: Cryptanalysis Question: Determing The Algorithm? ("Douglas A. Gwyn")
Re: Best, Strongest Algorithm ("Tom St Denis")
enumerating permutations ("Tom St Denis")
Re: RSA BRUTE FORCE (David Wagner)
Re: Tiny s-boxes ("Simon Johnson")
Re: Tiny s-boxes (David Wagner)
The novel _enigma_ by Robert Harris (Ed Pugh)
Re: enumerating permutations ("Henrick Hellstr�m")
Re: enumerating permutations ("Tom St Denis")
Re: Best, Strongest Algorithm (SCOTT19U.ZIP_GUY)
Re: A simple encryption algorithm based on OTP (John Savard)
----------------------------------------------------------------------------
From: Uwe Guenther <[EMAIL PROTECTED]>
Subject: Re: ISO 9796-1:1991
Date: Tue, 08 May 2001 23:13:24 +0200
Anders Thulin wrote:
>
> Uwe Guenther wrote:
>
> > I have to implement an client that uses german HBCI-Protocol
> > (HomeBankingComputerInterface). There are references to
> > the ISO 9796-1:1991(formating and signing). Since this standard
> > are withdrawn, there is no way to get the standard from ISO.
>
> I doubt that that should be impossible -- there has to be some possibility
> for checking up on old standards just to see what they said. Not necessarily
> by the standard sales channels.
>
> However, it is also an IEC standard, and judging from their
> catalogue (at http://www.iec.ch) it appears possible to order it there.
> As far as I can make out it has not been withdrawn from IEC, so don't
> check the withdrawn radio box when you search for it.
Thanks a lot -- this was the initial hint . Thanks!!!
--
Uwe
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Best, Strongest Algorithm
Date: Tue, 8 May 2001 20:52:18 GMT
"SCOTT19U.ZIP_GUY" wrote:
> IN short the NSA has to much power. The more power it has the more
> corrupt it will be come. I prefer a free people that don't need a
> big brother watching our every step.
NSA's not watching you; they're watching the people who are
out to do you harm. Big difference!
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: RSA BRUTE FORCE
Date: Tue, 8 May 2001 20:48:22 GMT
Joseph Ashwood wrote:
> ... I found that for values that are close together this
> works fairly quickly, but as the numbers get further apart the time grows
> exponentially ...
Hm, does that mean we have yet another constraint to add when
picking primes for RSA: Don't pick them too close together?
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Cryptanalysis Question: Determing The Algorithm?
Date: Tue, 8 May 2001 20:40:13 GMT
"Bo D�mstedt" wrote:
> > Bo D�mstedt" wrote:
> > > ... What you can do is to sequentially test different assumptions,
> Douglas Gwyn wrote:
> > If you have a whole team, they can test various possibilities in
> > parallel, and when one of them succeeds in making a definite break
> > into the system, the rest of the team can be retasked.
> Sorry, "sequentially" is humoristic. If you have a function
> with N bit input and N bit output, you may (in principle) implement
> that function with a table with 2^N rows, and store an N bit number
> on each row. Then there could be 2^( N*( 2^N)) different
> such functions.
> If you use an N-bit bit transposition, then there are N!=
> =N*(N-1)*(N-2)*...*2*1different possible transposition functions.
? No actual system can come close to implementing the general
mapping table (for reasonable N). Anyway, one does not search
across all possible mappings in a brute-force manner. Almost
all actual systems have structural regularities, and uncovering
these is the first task in cryptodiagnosis.
> The problem for the cryptanalyst is that efficient cryptanalysis
> methods directly exploit some structure in the target cipher.
> For an unknown cipher, these methods do not apply.
> The problem for the cryptographer, is to prevent the structure
> of the cipher to become known, if a cipher machine would fall
> into the hands of the enemy (Kerckhoffs principle). This may
> be accomplished using both cryptographic and implementation
> techniques and methods.
That's like saying the problem is to keep the enemy from
discovering the plaintext. It's the ultimate goal, but
in practice it is often not realized.
> Is it more clear now ?
I don't know; I thought the contrast between trying assumptions
sequentially and in parallel was clear to begin with.
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Best, Strongest Algorithm
Date: Tue, 08 May 2001 21:37:34 GMT
"Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> "SCOTT19U.ZIP_GUY" wrote:
> > IN short the NSA has to much power. The more power it has the more
> > corrupt it will be come. I prefer a free people that don't need a
> > big brother watching our every step.
>
> NSA's not watching you; they're watching the people who are
> out to do you harm. Big difference!
Time to play devils advocate here. Let's suppose that the NSA is out to spy
on US citizens. Why out of all 300 million of ya would they spy on *you*.
If you can answer that question you should fear the NSA otherwise.... :-0.
Something tells me Hollywood is only fuelling the ego's of some NSA types.
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: enumerating permutations
Date: Tue, 08 May 2001 21:42:35 GMT
I got bored in my College "Technical Math" class so I think I came up with a
way to enumerate permutations (I proved it works with 3 element perms). It
works like this.
You have N elements in the perm.
You have a list of N items called L initialized to hold 0 to N-1.
You have the output array of N items called S
You have an integer P of the form 0 <= P < N!
1. for I from N to 1 do
1.1 R = P mod I
1.2 S[R] = L[R]
1.3 Delete L[R] from the list R effectively making it one item shorter.
1.4 P = P div I
1.5 Loop.
It's not the fastest thing in the world but certainly simple to program.
With N <= 256 this is very fast but requires large numbers... The biggest
problem is if all of your P values are known to be in the range of 0..2^W
where 2^W << N! then it won't be as random as it could be.
One suggestion for smaller seeds is to use exponentiation... as in
G^seed mod N!. Obviously G should generate a large (if not maximal) group
in Z*q for some q that divides N! - 1.
--
Tom St Denis
---
http://tomstdenis.home.dhs.org
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: RSA BRUTE FORCE
Date: 8 May 2001 21:51:00 GMT
Douglas A. Gwyn wrote:
>Hm, does that mean we have yet another constraint to add when
>picking primes for RSA: Don't pick them too close together?
No, because picking primes randomly ensures they won't be too close
together (with probability so close to 1 that if you get find a violation
of this claim, I want you picking my lottery tickets).
------------------------------
From: "Simon Johnson" <[EMAIL PROTECTED]>
Subject: Re: Tiny s-boxes
Date: Tue, 8 May 2001 23:00:24 +0100
Brian McKeever <[EMAIL PROTECTED]> wrote in message
news:DTLJ6.321$[EMAIL PROTECTED]...
> "Simon Johnson" <[EMAIL PROTECTED]> wrote in message
> news:9d5vn3$hds$[EMAIL PROTECTED]...
> > Of course the next question is, can we make an algebraic 64x64 s-box
that
> > behaves as a random premutation and can not be 'decomposed' into small
> > s-boxes to be analysed?
>
> I've played around a little bit with something similar to what you're
> suggesting. Inspired by the IDEA 16x16 algebraic s-box, I tried to come
up
> with ways to make huge substitutions that had enough algebraic structure
> such that they were computable (vs having to be implemented as a lookup
> table), but which were large enough that they were probably pretty
good(TM).
> I have an extraordinarily unimpressive web page at
> http://www.geocities.com/reveekcm_nairb/maverick/Maverick.html that
> describes it a little bit. The basic idea was to find a large group for
> which the group operation can be performed without much trouble, and for
> which there exist easily implemented functions to and from vectors of
bits.
> For the algorithm on the web page, I used the multiplicative group of
GF(p),
> for p of the form k*2^(2^n)+1 (where IDEA has k=1, n=4).
>
> As for your point about not being decomposable, I agree that it's
desirable
> (and in fact, you probably wouldn't want it to be 'too close' to a
> decomposable transform, either), but I don't know how to check for that
> given a modest-sized s-box, much less a huge one. Any ideas?
>
> Brian
Well, I've thought about this a bit more....
A friend told me that (a/x) where x is in GF(2^w) and a and is a fixed
polynomials gives optimal performance against differential and linear
cryptanalysis. Computing a/x gets slower as w gets larger so we can't make w
stupidly large... this said at w=32 we need 2^64 operations to recover the
entire s-box structure with respect to each attack.
This is better than randomly selected boxes because we still know that the
DP-max and LP-max across the boxes are low.. without knowing the extract
structure ( I hope =) ).
Random boxes have problems... we don't need a full xor-diff table to mount
an attack.. if we did 2^32 work on one difference, say x.. and found that
x-> y with high probability.. we have cracked the cipher... though with
large mappings this is unlikely.
Simon.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Tiny s-boxes
Date: 8 May 2001 21:57:45 GMT
Simon Johnson wrote:
>A friend told me that (a/x) where x is in GF(2^w) and a and is a fixed
>polynomials gives optimal performance against differential and linear
>cryptanalysis.
Sure, this is the idea behind the Rijndael S-box and many others.
On its own, this is pretty awful against rational interpolation attacks,
though...!
------------------------------
From: [EMAIL PROTECTED] (Ed Pugh)
Subject: The novel _enigma_ by Robert Harris
Date: 8 May 2001 21:52:04 GMT
Reply-To: [EMAIL PROTECTED] (Ed Pugh)
[Note: I am also posting this to soc.history.war.world-war-ii
which is a moderated newsgroup; the post is still pending to
appear on that newsgroup.]
Hi.
I just re-read (2nd time) Robert Harris' excellent novel,
_enigma_ (and, no, that is not a typo; the title name begins
with a lower-case 'e'). It is a very good read and I would
recommend it to anyone interested in the history of WW II
cryptology or in the work of the Bletchley Park cryptanalysts.
This is a fictional novel about a Bletchley Park cryptanalyst
during WW II. It takes place around February to April, 1943.
I think, however, that there may be a few technical inaccuracies
in the novel. I don't know anything about the details of how
Bletchley Park operated, so I cannot judge the accuracies of the
parts that describe such details. However, I did find three
items in the novel that I thought might be a bit odd.
[ Each chapter of the book is divided into numbered sections.
The page and line numbers that I quote are from the hard-covered
first edition, published by Random House, New York
(ISBN 0-679-42887-9). ]
1. U.S.A. B-17s stationed in Britain.
Chapter 1, Section 2, page 16, lines 15-18.
Near the beginning of the novel, the hero, Tom Jericho, is
walking toward an American air field in Britain, near Cambridge
in mid-March, 1943. He is enjoying a sunny sky:
".. the sky was a glory -- a pure blue dome above the flat
landscape of East Anglia, filled for miles with the silver
specs of aircraft and the white scratches of contrails."
Would Allied war planes have been silver by this time, or would
they have still been painted olive-green?
Also, I always thought that only jet engine planes would form
contrails. Would piston-prop driven airplanes form white
contrails in the sky?
2. German U-boats and four-rotor Enigma machines.
Chapter 6, very end of Section 1, page 244, lines 25-27.
In this part, a German U-boat (U-653) is about to make a report
of an Allied convoy contact. So, the U-boat radioman is about
to turn on his equipment, including a four-rotor Enigma (the
type that the Bletchley Park people called "Shark"):
"In his cubbyhole next to the captain's berth, the radioman
pressed his switches. The Enigma came on with a hum."
My understanding is that an Enigma was a DC powered machine.
There were no electronics in an Enigma (i.e. no "valves" or
"tubes"). Also, I don't think there were any motors, relays or
solonoids. I thought that the only electrical devices in the
Enigma were the keyboard switches, the light bulbs and the
"Steckerboard" plugs and jacks. The army field Enigmas were
certainly powered by batteries. (I had the pleasure of actually
operating a three-rotor Enigma at the Canadian Museum of Science
and Technology here in Ottawa last year. It was powered by a
dry-cell battery.)
Did Germain U-boats have AC electric power systems? If so,
then did the U-boat Enigmas have an AC power supply? In short,
would a U-boat Enigma "hum" when it was turned on? If so, then
what, exactly, would cause the "hum"?
3. Three-rotor Enigma Stekcerboard.
Chapter 6, Section 5, page 268, lines 9-11.
In this part, Jericho (the hero) has locked himself into a
storage vault in the basement of the Bletchley Park "Mansion",
and is about to set up a three-rotor Enigma to decrypt a series
of messages involving a German army unit (because he cannot gain
access to any of the Type-X machines that the park personell
normally use to decrypt German Enigma messages).
While setting it up, he is about to plug in the Steckerboard
connections:
"The next ten letter pairs represented the cross-pluggings he
needed to make on the steckerboard on the back of the Enigma."
Any Engmas or pictures of Enigmas that I have seen always had
the Steckerboard on the FRONT of the Enigma. Were there any
Army Enigma machines that had the Steckerboard on the back?
----
If you follow-up to this newsgroup, that's fine. I would
appreciate it if you could also please CC your follow-ups
to [EMAIL PROTECTED]
Thanks and regards,
--
Ed Pugh, <[EMAIL PROTECTED]>
Ottawa (Richmond), Ontario, Canada
"Bum gall unwaith-hynny oedd, llefain pan ym ganed."
(I was wise once, when I was born I cried - Welsh proverb)
------------------------------
From: "Henrick Hellstr�m" <[EMAIL PROTECTED]>
Subject: Re: enumerating permutations
Date: Wed, 9 May 2001 00:04:06 +0200
You just reinvented one of the elements of the SteakCipher key schedule. Cf
http://www.stremsec.com/combutil.pas
I don't know if I was the first to actually use this algorithm in this way.
Probably not. A similar algorithm was described by Knuth.
--
Henrick Hellstr�m [EMAIL PROTECTED]
StreamSec HB http://www.streamsec.com
"Tom St Denis" <[EMAIL PROTECTED]> skrev i meddelandet
news:fLZJ6.47218$[EMAIL PROTECTED]...
> I got bored in my College "Technical Math" class so I think I came up with
a
> way to enumerate permutations (I proved it works with 3 element perms).
It
> works like this.
>
> You have N elements in the perm.
> You have a list of N items called L initialized to hold 0 to N-1.
> You have the output array of N items called S
> You have an integer P of the form 0 <= P < N!
>
> 1. for I from N to 1 do
> 1.1 R = P mod I
> 1.2 S[R] = L[R]
> 1.3 Delete L[R] from the list R effectively making it one item shorter.
> 1.4 P = P div I
> 1.5 Loop.
>
> It's not the fastest thing in the world but certainly simple to program.
> With N <= 256 this is very fast but requires large numbers... The biggest
> problem is if all of your P values are known to be in the range of 0..2^W
> where 2^W << N! then it won't be as random as it could be.
>
> One suggestion for smaller seeds is to use exponentiation... as in
>
> G^seed mod N!. Obviously G should generate a large (if not maximal) group
> in Z*q for some q that divides N! - 1.
> --
> Tom St Denis
> ---
> http://tomstdenis.home.dhs.org
>
>
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: enumerating permutations
Date: Tue, 08 May 2001 22:12:57 GMT
"Henrick Hellstr�m" <[EMAIL PROTECTED]> wrote in message
news:9d9qj2$nnd$[EMAIL PROTECTED]...
> You just reinvented one of the elements of the SteakCipher key schedule.
Cf
> http://www.stremsec.com/combutil.pas
>
> I don't know if I was the first to actually use this algorithm in this
way.
> Probably not. A similar algorithm was described by Knuth.
Keen.
Tom
>
> --
> Henrick Hellstr�m [EMAIL PROTECTED]
> StreamSec HB http://www.streamsec.com
>
> "Tom St Denis" <[EMAIL PROTECTED]> skrev i meddelandet
> news:fLZJ6.47218$[EMAIL PROTECTED]...
> > I got bored in my College "Technical Math" class so I think I came up
with
> a
> > way to enumerate permutations (I proved it works with 3 element perms).
> It
> > works like this.
> >
> > You have N elements in the perm.
> > You have a list of N items called L initialized to hold 0 to N-1.
> > You have the output array of N items called S
> > You have an integer P of the form 0 <= P < N!
> >
> > 1. for I from N to 1 do
> > 1.1 R = P mod I
> > 1.2 S[R] = L[R]
> > 1.3 Delete L[R] from the list R effectively making it one item shorter.
> > 1.4 P = P div I
> > 1.5 Loop.
> >
> > It's not the fastest thing in the world but certainly simple to program.
> > With N <= 256 this is very fast but requires large numbers... The
biggest
> > problem is if all of your P values are known to be in the range of
0..2^W
> > where 2^W << N! then it won't be as random as it could be.
> >
> > One suggestion for smaller seeds is to use exponentiation... as in
> >
> > G^seed mod N!. Obviously G should generate a large (if not maximal)
group
> > in Z*q for some q that divides N! - 1.
> > --
> > Tom St Denis
> > ---
> > http://tomstdenis.home.dhs.org
> >
> >
>
>
>
>
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Best, Strongest Algorithm
Date: 8 May 2001 22:26:23 GMT
[EMAIL PROTECTED] (Douglas A. Gwyn) wrote in <[EMAIL PROTECTED]>:
>"SCOTT19U.ZIP_GUY" wrote:
>> IN short the NSA has to much power. The more power it has the more
>> corrupt it will be come. I prefer a free people that don't need a
>> big brother watching our every step.
>
>NSA's not watching you; they're watching the people who are
>out to do you harm. Big difference!
>
I wish I could belive that. In the cold war that was
there job. But if you look at the UK my understanding is
crime is going up. My own theory is when the government
can't trust its own people. Then thats the time that country
goes down. I feel if the NSA was full of honest hard working
people they would have corrected the corruption in government
maybe they could have helped put Clinton in prison. Or told
people the truth about Waco. So others would not have gone
high order by the lack of honest govenment invovlement.
In the cold war the NSA was our friend. But know the main
job is keeping secrets of government corruption from us
and helping to perpetuate the crooked status quo. Yes
the NSA had its place. But having worked my self for uncle
I honestly belive the fact of being forced to lie so often
is in the long run a corrupting influence. Where the truth
no longer manners except to fool dumb people that need to
be controlled.
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: [EMAIL PROTECTED] (John Savard)
Subject: Re: A simple encryption algorithm based on OTP
Date: Tue, 08 May 2001 22:51:31 GMT
On Tue, 08 May 2001 16:42:08 +0530, "Siva Prasad Gummadi [T]"
<[EMAIL PROTECTED]> wrote, in part:
> Since this is basically OTP I think it should be a good algorithm.
No, it isn't.
The problem is that only the original key is *truly* unknown. Yes, you
also don't know the first plaintext sent with it.
But whether you use the original key again to encipher the next block
of plaintext, _or_ you use the first plaintext sent, _either_ way you
are now exposing the key to attack.
If you use more secure operations than a simple XOR, you might still
be able to produce something secure from this general idea, but it
won't be secure the way the OTP is.
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
******************************
