Cryptography-Digest Digest #455, Volume #14 Sun, 27 May 01 07:13:01 EDT
Contents:
Re: James Felling: Sorry to break your bubble (Anthony Stephen Szopa)
RSA keysize doubling techniques (Uenal Mutlu)
Re: Good crypto or just good enough? (Mok-Kong Shen)
Re: A generic feistel cipher with hash and gf(257) mixers (Jim Steuert)
----------------------------------------------------------------------------
From: Anthony Stephen Szopa <[EMAIL PROTECTED]>
Crossposted-To: alt.hacker,talk.politics.crypto
Subject: Re: James Felling: Sorry to break your bubble
Date: Sun, 27 May 2001 02:47:23 -0700
HiEv wrote:
>
> Anthony Stephen Szopa wrote:
> >
> > James Felling: Sorry to break your bubble
>
> First of all, the phrase is "burst your bubble" not "break your bubble".
>
> > Reference: OAP-L3: "The absurd weakness."
>
> And we decided to make this a new thread why? I guess you needed to
> stroke your own ego more by putting down the one guy who was posting
> decent responses to your lame ASS [that's Anthony's initials, not a
> swear word].
>
> I should also note, that after breaking off this new thread you proceed
> to try and trash the guy, but you don't even quote him once! If we want
> to follow you we now have to go back to another thread.
>
> Should I mention the lousy cross post too?
>
> > Tell me, do you have very many stupid people who pay you money for
> > expounding such logic as you have demonstrated in your past three
> > or four posts? Wait! Don't answer that right now. First read the
> > following.
>
> (gag, choke, sputter)
>
> Pot: Pot to Kettle, Pot to Kettle, come in Kettle!
> Kettle: Kettle here.
> Pot: You are black.
>
> > As you will see from looking at the first 105 permutations that the
> > first 5 digits are: 0 1 2 3 4. No matter how many times you run
> > your 105! process these first five digits of the group of 105
> > permutations will always be the same.
>
> Oh, yeah, easy to follow the context here, eh? Roughly, what was said
> earlier was that Anthony would have a problem with some numbers not
> being shuffled. His response (above) is that the suggested method would
> have the same problems.
>
> He doesn't address the possibility that his algorithm may have the same
> problem.
>
> > Now if you are aware of the way OAP-L3 works, you will know that
> > this will result in very very poor random digit output: basically
> > unusable.
>
> Which is how just about everyone feels about it in the first place.
>
> > You will also find further redundancy in the sixth digit. Over a
> > group of just 105 permutations this is unacceptable with OAP-L3.
> [snip rambling diatribe about how the suggested fix won't work]
>
> Still nothing about the existing problem mentioned by James.
>
> > I could pursue this analysis further but your suggestion of my
> > "design flaws" has turned out to be nothing more than your myth and
> > your suggestion to correct these fantastic "flaws" has turned out to
> > be a fraud.
> >
> > I sure hope everyone is listening.
> [snipped sequential list of permutations from 0 to 104]
>
> And where do you disprove the design flaw he pointed out again? I don't
> see it here.
>
> > Tell me, do you have very many stupid people who pay you money for
> > expounding such logic as you have demonstrated in your past three
> > or four posts? Wha'da ya say?
>
> If I needed someone in the encryption arena, I'd be more likely to hire
> him than you. He's maintained a level head thoughout most of this,
> while you keep going to insults.
>
> I admit I haven't been free of insults in this message, but it doesn't
> seem like you pay much attention to reason.
>
> > If you have two encryption software methods I suggest you consider a
> > corollary of Occum's Razor: choose the one that is simplest and
> > easiest to understand in its entirety over the one you cannot
> > comprehend with certainty to the fullest.
>
> Argh! It's "Occam's Razor" not "Occum's Razor", and your version seems
> to imply you shouldn't try to figure things out if you don't understand
> them. Besides, simple != secure. Neither does complex mean secure,
> thoroughly examined for weaknesses with none found suggests that it is
> secure though. However you seem to get upset when anyone says that they
> think they see a weakness.
>
> I'm glad you aren't a ship captain. "Captain, there is a leak on one of
> the lower decks!" "Have that man thrown overboard! How dare he talk
> about my ship like that. It's treason!"
>
> Nowhere in this huge insult of this message do you address whether
> James's fix is necessary, you merely attack him. That does not speak
> well of your algorithm.
>
> > (Damn, that felt good. Maybe I'm ready for Bruce?)
>
> Yes, I'm sure insulting people who attempt to make helpful suggestions
> makes you feel like a big man. Heaven forbid you should actually listen
> to someone.
>
> If your product can't take any criticism without you breaking down into
> insults, do you really think that people are going to buy/use it?
>
> --
> "Outlook not so good." That magic 8-ball knows everything! I'll ask
> about Exchange Server next.
Actually I did post this reply to his post in the original thread.
I posted it here as well because I know that some readers haven't
been following that original thread.
(Be sure to read the last 5 lines of this reply post.)
I am not going to go back and pull out my politeness handbook but he
is the one who came up with the "nasty" flaw comment. When you start
horse playing around with a gorilla I would expect the play to get a
little rough.
I think it is significant when someone says that I have egg on my
face then gives me a suggestion to fix or improve my design then
come to find out that his suggestion is so completely bogus as to
nearly defy description although I did manage to describe why his
suggestion is all washed up.
So with my stunning proof that he doesn't know what he is talking
about with his own suggestion as to what I should do or how he has
come up with a better mouse trap, how can you continue to blindly
give his original comments anything but skepticism?
But you answered this question in your own post: "Which is how just
about everyone feels about it in the first place." (I presume you
are referring to OAP-L3.) You have chosen to "feel" instead of
think.
Don't you have a brain? Why don't you use it then? He clearly
doesn't know what he is talking about here yet you still "feel" his
original comments to be valid.
I responded that his fixed point argument is immaterial. When a
different process is run these fixed points are no more.
If his point(s) is/are valid then when the final OTPs are generated
then you can surely point out to us where and how and why these
alleged "flaws" have affected the OTP output where you can determine
something, anything, etc. (keep hoping) that you can claim has
compromised the output.
To claim there is a flaw requires that one be able to point it
out. Point out any flaw in the final OTP output as a result of these
(immaterial) "flaws." If they are immaterial then they are not
"flaws." Perhaps a better phrase would be inconsequential anomalies
or immaterial peculiarities of OAP-L3.
If you are saying that these "flaws" are material to the final OTP
output then I will ask you as I ask everyone: prove it in the
slightest sense. Give us a clue. Give us something to chew on.
The recommended use of OAP-L3 is to randomly choose the processes to
run and randomly choose what order to run them in and to input
random data into each process.
Check this out. Here are the first 105 permutations from the file
after I have run this particular process ten times with random
input for each run. Now compare this output to what JF suggested.
Array number: 0 0 1 2 3 4 5 6 7 8 9
Array number: 1 0 1 2 3 4 5 6 7 9 8
Array number: 2 0 1 2 3 4 5 6 8 7 9
Array number: 3 0 1 2 3 4 5 6 8 9 7
Array number: 4 0 1 2 3 4 8 9 6 7 5
Array number: 5 0 1 2 4 5 9 7 8 3 6
Array number: 6 0 1 2 4 6 3 5 8 9 7
Array number: 7 0 1 2 4 6 3 8 9 7 5
Array number: 8 0 1 2 5 4 3 6 8 7 9
Array number: 9 0 1 2 5 6 3 4 8 7 9
Array number: 10 0 1 2 7 5 9 6 4 3 8
Array number: 11 0 1 3 4 5 7 8 2 9 6
Array number: 12 0 1 3 4 6 2 9 5 8 7
Array number: 13 0 1 3 4 6 2 9 7 5 8
Array number: 14 0 1 3 8 6 5 9 2 7 4
Array number: 15 0 1 4 3 2 7 5 6 9 8
Array number: 16 0 1 4 3 2 8 6 7 5 9
Array number: 17 0 1 4 3 6 5 7 2 8 9
Array number: 18 0 1 5 2 3 9 6 8 4 7
Array number: 19 0 1 5 2 3 9 7 6 4 8
Array number: 20 0 1 5 2 6 3 7 4 8 9
Array number: 21 0 1 5 3 7 2 9 4 8 6
Array number: 22 0 1 5 4 9 6 7 8 2 3
Array number: 23 0 1 5 4 9 8 3 2 6 7
Array number: 24 0 1 6 7 4 8 9 2 3 5
Array number: 25 0 1 6 7 4 8 9 2 5 3
Array number: 26 0 1 6 7 4 8 9 3 2 5
Array number: 27 0 1 6 9 8 4 5 3 2 7
Array number: 28 0 1 6 9 8 7 2 3 4 5
Array number: 29 0 1 7 2 8 6 9 4 3 5
Array number: 30 0 1 7 3 6 2 8 4 5 9
Array number: 31 0 1 7 6 2 3 9 5 4 8
Array number: 32 0 1 7 6 2 4 5 9 8 3
Array number: 33 0 1 7 6 2 4 8 3 9 5
Array number: 34 0 1 7 6 4 2 3 9 8 5
Array number: 35 0 1 7 6 4 2 5 3 8 9
Array number: 36 0 1 7 8 3 2 6 9 5 4
Array number: 37 0 1 7 8 3 4 5 9 6 2
Array number: 38 0 1 8 2 9 4 5 3 7 6
Array number: 39 0 1 8 3 2 6 9 5 4 7
Array number: 40 0 1 8 3 2 7 4 6 5 9
Array number: 41 0 1 8 4 5 6 2 3 9 7
Array number: 42 0 1 9 7 5 3 4 8 2 6
Array number: 43 0 1 9 7 5 3 4 8 6 2
Array number: 44 0 1 9 7 5 3 6 2 4 8
Array number: 45 0 1 9 8 5 7 2 3 4 6
Array number: 46 0 2 1 5 6 4 9 8 3 7
Array number: 47 0 2 1 5 6 7 8 9 4 3
Array number: 48 0 2 1 6 5 8 3 7 9 4
Array number: 49 0 2 1 7 9 6 8 3 4 5
Array number: 50 0 2 1 7 9 6 8 3 5 4
Array number: 51 0 2 1 9 3 7 6 5 8 4
Array number: 52 0 2 1 9 4 5 3 8 7 6
Array number: 53 0 2 1 9 4 5 6 8 7 3
Array number: 54 0 2 1 9 5 7 8 6 3 4
Array number: 55 0 2 4 1 6 3 9 8 7 5
Array number: 56 0 2 4 3 1 7 5 9 6 8
Array number: 57 0 2 4 3 1 7 6 8 9 5
Array number: 58 0 2 4 3 1 7 9 5 8 6
Array number: 59 0 2 4 3 5 9 7 6 1 8
Array number: 60 0 2 4 3 6 5 8 1 7 9
Array number: 61 0 2 4 9 5 1 7 6 8 3
Array number: 62 0 2 4 9 5 1 7 8 3 6
Array number: 63 0 2 4 9 5 1 7 8 6 3
Array number: 64 0 2 4 9 5 1 8 3 6 7
Array number: 65 0 2 4 9 6 3 8 7 5 1
Array number: 66 0 2 5 1 7 6 4 8 9 3
Array number: 67 0 2 5 3 9 8 4 7 6 1
Array number: 68 0 2 5 4 9 8 6 3 7 1
Array number: 69 0 2 6 1 9 5 7 8 3 4
Array number: 70 0 2 6 9 3 1 8 7 4 5
Array number: 71 0 2 6 9 3 1 8 7 5 4
Array number: 72 0 2 6 9 3 4 1 8 7 5
Array number: 73 0 2 7 1 6 5 8 3 9 4
Array number: 74 0 2 7 1 6 5 8 4 3 9
Array number: 75 0 2 7 1 6 5 8 4 9 3
Array number: 76 0 2 7 1 6 5 8 9 3 4
Array number: 77 0 2 7 1 9 8 5 4 6 3
Array number: 78 0 2 7 3 1 8 4 9 5 6
Array number: 79 0 2 8 3 6 4 1 9 7 5
Array number: 80 0 2 9 4 3 8 6 7 5 1
Array number: 81 0 2 9 4 8 6 7 5 3 1
Array number: 82 0 2 9 4 8 7 1 3 5 6
Array number: 83 0 2 9 4 8 7 1 3 6 5
Array number: 84 0 2 9 4 8 7 3 1 5 6
Array number: 85 0 2 9 6 1 3 7 8 5 4
Array number: 86 0 2 9 6 1 5 3 7 4 8
Array number: 87 0 2 9 6 1 5 3 7 8 4
Array number: 88 0 2 9 6 1 8 7 5 4 3
Array number: 89 0 2 9 6 3 4 5 8 1 7
Array number: 90 0 2 9 8 6 5 1 3 4 7
Array number: 91 0 2 9 8 6 5 1 3 7 4
Array number: 92 0 3 1 8 4 6 9 2 7 5
Array number: 93 0 3 1 8 5 7 4 2 6 9
Array number: 94 0 3 1 8 5 7 4 6 9 2
Array number: 95 0 3 1 8 5 7 9 4 2 6
Array number: 96 0 3 1 8 9 7 2 4 5 6
Array number: 97 0 3 1 9 5 6 2 8 7 4
Array number: 98 0 3 4 6 9 5 1 7 8 2
Array number: 99 0 3 4 8 1 7 5 6 2 9
Array number: 100 0 3 4 8 5 7 2 9 1 6
Array number: 101 0 3 4 8 5 9 6 1 2 7
Array number: 102 0 3 4 8 5 9 6 1 7 2
Array number: 103 0 3 4 8 6 2 1 5 9 7
Array number: 104 0 3 4 9 2 5 6 1 7 8
JFs suggestion will never ever even come close to this. Every
single one of his 105 permutation groups will always have the first
5 or 6 digits exactly the same no matter how many times he runs
his process.
I seem to have concretely defended my position. If it is not clear
enough then tell us a problem you have with OAP-L3 and I will address
it further for you.
JFs suggestion that my groups are 105 permutations is misleading.
Technically this is true when you look only at one specific running
of the process. But the effect is cumulative over the entire
3,628,800 permutation set. The more the process is run the more the
effected group is expanded: the entropy over the entire permutation
set increases.
His suggestion was exactly 105 permutations long and remained so no
matter how many times he ran the process. The entropy was confined
within each 105 permutation group within the entire permutation set.
As you said, my process also shows some redundancy. This is inherent
in this process. But it does add entropy over the entire permutation
set. You can quantify the entropy. You know exactly where you stand.
When you randomly run processes and input random data in each process
you can calculate what the output entropy is. And each process
increases the entopy over the entire permutation set.
At first glance you may not be too impressed with the above 105
permutations. Keep in mind that since you are randomly running each
process it is unlikely that you will run the Mix a Mixfile process 10
times in a row. But when you do run it it will add the usual entropy
to the output file. And it makes a big difference in what sequence
or order you run the processes in.
And keeping in mind how the permutations transform each other and
index or reference each other to generate random digit output you
will realize that the cumulative entropy and inherent inefficiency
designed into OAP-L3 will result in very good random number
distributions. There are utility programs that come with OAP-L3
that allow you to quantify the random number output distribution.
The random output numbers are excellent.
No single process was designed to randomly shuffle the entire
permutation set. Each was designed to add a modest amount of
entropy. And in combination all the processes were designed to at
least effectively reach enough of the possible key space to make
OAP-L3 practicably unbreakable: quite so.
Now keep in mind that this is just the first half of the overall
process. Once you use three thoroughly and randomly shuffled
MixFiles to generate random digits and only use about a random 70%
of these digit triplets you further thoroughly reprocess these
random number (000 - 255) files.
If you can even reasonably suggest any possibility of some sort of
flaw in the final OTP files generated, again, we would all like to
hear of it.
By the way, I wouldn't put it past JF to have made his post knowing
all along that his suggestion was bogus. He might just have wanted
to see if I was intelligent enough to see through it.
But in so doing he has heard from many of you, as well.
Cheers.
(Get a sense of humor.)
------------------------------
From: Uenal Mutlu <[EMAIL PROTECTED]>
Crossposted-To: sci.math.num-analysis
Subject: RSA keysize doubling techniques
Date: Sun, 27 May 2001 00:59:11 +0200
I'm looking for methods for extending the capacity of
an RSA Crypto Accellerator (HW) by the factor 2.
It has two registers of each 1120 bits and can perform
modular and non-modular multiplication, addition,
subtraction, reduction, logical XOR and shift operations.
This accellerator can handle RSA key sizes of up to 1024 bit.
I would like to use a wrapper library around this
to extend the capacity to 2048 bits. Are there any
doubling algorithms to realize this?
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Good crypto or just good enough?
Date: Sun, 27 May 2001 12:59:40 +0200
"Douglas A. Gwyn" wrote:
>
> "SCOTT19U.ZIP_GUY" wrote:
> > The NSA wants people to use [Rijndael] for several years.
>
> I'm sure the NSA would be happiest if everybody used the *same,
> standard* cryptosystem, only because their cryptanalysts could
> concentrate resources on cracking just the one system instead
> of spreading them thinly across numerous commonly-used systems.
The advantages of having a standard highly outweigh the
disadvantages. This is invariably true everywhere in
technology and I believe crypto is no exception to that.
After all, if one thinks that what is offered by a standard
is not sufficient, there are always ways open to have
something in addition.
M. K. Shen
------------------------------
From: Jim Steuert <[EMAIL PROTECTED]>
Subject: Re: A generic feistel cipher with hash and gf(257) mixers
Date: Sun, 27 May 2001 07:09:03 -0400
Thanks David,
I understand your proof. It is very clear. I now understand
meet-in-the-middle
attacks. I now ask whether one of these fixes is worthwhile:
a) Use at least one more key part, and blend it in. The attack is thus
on =>(xor k1)=>H=>(xor k2)=>J=>(xor k3)=>K=>(xor k4)=>
The mitm attack would generate the set of k2(1 per k1) and
the set of k3(1 per k4). However, the set after J would
be of order k3(1 per (k1,k2)) or 2^48 And by breaking the key into
more parts, the order could be made even higher.
b) Re-use the parts of the key at the various stages, so that at each
stage i, the key itself (ki) is a 32-bit wide hash si of the
entire original key,
but xor'ed with only one of the 3 digest-width variables.
You had implied this in your statement "since you are only using
each part of the key once"... This should prevent intersections.
While the original specification of my cipher was flawed, is there
anything fundamentally wrong with the methodology or recipe, given those
(important) fixes, to generate a reasonable cipher? I''ll rephrase the
methodology or recipe or class of ciphers as:
A) Use multiple stages (at least 5) of invertible hashes H,J,K,L,M,...
B) Form at least 5 different derived keys d1,d2,d3,d4,d5, using
5 "different" 32-bit-output compression hashes of the entire key.
C) After each stage, blend in a part of a derived key mixed in via
partial-width
xor (or some other invertible mixer) in. By partial width is
meant
xoring with only one out of three of the full digest
variable width (say, with just digest variable b out of (a,b,c)
).
D) Shake, Stir and Serve (just kidding)
My main point is that there can be simple recipes, this being one of the,
that if followed, will provide a reasonable cipher, and still provide lots
of room for creativity. I certainly erred, and got corrected on some
of the recipe steps.
David Wagner wrote:
> Jim Steuert wrote:
> >Can you tell me again how you would go about breaking this??
>
> In my preferred notation, the cipher is
> E_{k1,k2,k3}(x) = I(H(G(F(x) xor k1) xor k2) xor k3))
> where F,G,H,I are fixed invertible non-key-dependent operations.
>
> First, note that F and I are irrelevant. Given a known plaintext
> pair (x,y), we can strip them off to produce a known plaintext pair
> (x',y') [where x=F(x), y'=I^{-1}(y)] for the following reduced cipher:
> E'_{k1,k2,k3}(x) = H(G(x xor k1) xor k2) xor k3
> For simplicity of description, I'll describe the attack as an attack
> on E', but of course any such attack can be converted into an
> attack on the full cipher E (the description gets wordier, but
> the complexity of the attack does not increase appreciably).
>
> We can break E' with a meet-in-the-middle attack, as follows.
> Suppose we have two pairs of known plaintext, (p,c) and (p',c').
> Define functions f and g by f(k1) = G(p xor k1) xor G(p' xor k1),
> g(k3) = H^{-1}(c xor k3) xor H^{-1}(c' xor k3). Note that
> f(k1) = g(k3).
> (Do you see why?) Therefore, the attack can proceed as follows.
> Compute g(k3) for every value of k3, and store the result in a
> lookup table keyed on the result, so that given z we can quickly
> find k3 such that g(k3) = z, if such a k3 exists. This can be done
> with 2^32 operations, and the resulting table consumes 2^32 units
> of storage. Next, compute f(k1) for each k1 and check whether there
> is a solution to f(k1) = g(k3) by looking up f(k1) in the table you
> just computed. You expect that when k1 is guessed wrongly, f(k1)
> will not exist in the table. Certainly when k1 is guessed correctly,
> it will appear in the table, and the correctness of the guess can
> be confirmed with a few more trial decryptions (one can recover
> k2 via the equation k2 = G(p xor k1) xor H^{-1}(c xor k3)).
> So this completely breaks the cipher with 2^32 time and space.
------------------------------
** 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
******************************
