Cryptography-Digest Digest #350, Volume #12 Thu, 3 Aug 00 14:13:01 EDT
Contents:
Re: Small block ciphers (Mok-Kong Shen)
Re: Kill my cipher (Mark Wooding)
Re: OTP using BBS generator? (Mark Wooding)
Re: Small block ciphers (Mack)
Re: What is the word on TC5? (Mark Wooding)
Re: OTP using BBS generator? (Mack)
Re: OTP using BBS generator? (lordcow77)
Re: OTP using BBS generator? (Tim Tyler)
Cracking RC4-40 in FPGA hardware ("Paul Morris")
Re: IV for arfour ("Andreas Sewe")
Re: JavaCard vs Multos security (Tom Anderson)
Re: Elliptic Curves encryption (Mike Rosing)
Re: Pegwit - "Weak" ECC with GF(2^m), m composite? (Mike Rosing)
Re: microwave cd (John Hascall)
----------------------------------------------------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Small block ciphers
Date: Thu, 03 Aug 2000 18:55:26 +0200
Mack wrote:
>
> >Mack wrote:
> >
> >> Mok-Kong.Shen wrote:
> >> >We are doing at the bit level, aren't we? If one substitutes the known
> >> >bits into the T terms, how can one say that an expression involving
> >> >the T terms has T unknowns instead of B unknowns? (Compare
> >> >my example quoted below.)
> >> >
> >>
> >> Yes it is a bit level representation. The expression is developed before
> >> we have known bits. Once those bits are known the expression can
> >> be reduced. ie. without a known pair we develop the expression of
> >> the cipher in ANF in terms of equations of output with input and
> >> key being unknown. So we have T unknowns at this point. Once
> >> we have a known pair we can reduce this to a set of equations in
> >> K unknowns by substituting the known bits for the B variables.
> >>
> >> Now it is conceivable to develop a set of equations for K unknowns
> >> by assuming a certain plaintext. This results in a chosen plaintext
> >> attack rather than a known plaintext attack.
> >
> >Whether known-plaintext or chosen plaintext, the input bits are
> >known. Hence I would say that in both cases we have B equations
> >and K unknowns. Theoretically, with more plaintext and ciphertext
> >pairs, the K unknowns can be solved. Practically, this could be
> >a different issue. Anyway, I don't know whether useful and general
> >assertiions could be made that are valid in all situations.
>
> In the final product we are solving the B equations in K unknowns.
> In developing those equations we have to make a choice of whether
> we are doing a known-plaintext attack in which case we need to
> deal with B+K variables until we have the known plaintext to fill
> in the inputs. Or we can pick a set of inputs and develop the equations
> using those inputs in which case we never have to deal with the
> B inputs as variables. If time is not an issue then we can
> develop any known-plaintext into a set of equations.
Perhaps I misunderstood. One has some complicated boolean
expression as a function. This is purely formal. When we do
the solution, we have from the known-plaintext the B input
values. We substitute these in. The result can then be
subjected to the solution process which tries to determine
the value of the K variables. As far as I can see it doesn't
differ from, say, the solution of a set of linear equations
M*X = C. The values of the vector C are set in at solution
time (dynamically) and then the elimination process, e.g.
that of Gauss, begins. BTW, here the elements of C are
never considered to be 'variables' in any sense, even though
values have to be substituted into them before the solution
process starts (before substitution they are of course unknown).
So I surmise that probably we have essential terminological
disparities.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Kill my cipher
Date: 3 Aug 2000 16:49:06 GMT
Martin 'SirDystic' Wolters <[EMAIL PROTECTED]> wrote:
> It's a 16 round Feistel Cipher, which uses 16 subkeys, generated like
> this:
[snip]
> where ky[0] is a 32 Bit User key and rot(x,y) means a Left rotation of
> x by y bits, defined as:
[snip]
Oooh. 32-bit security! Setting our sights a bit high here, aren't we?
> This is the f-function it uses:
>
> int f(int in,int k)
> {
> int r,r2,o,o2;
> in=~in; [1]
> r=k&31; [2]
> o=rot(in,r)^k; [3]
> r2=o&31; [4]
> o2=rot(o,r2)^k; [5]
> o2=~o2; [6]
> return o2;
> }
Oh. Well, the only nonlinearity is the rotations, and the only
differentially-active component is the second rotation. This
transformation leaks the parity of k; the whole cipher leaks the parity
of plaintext, given one known plaintext. Rotating a value according to
its own low-order bits is a bad idea. It's also nonbijective, although
I can't yet see a way to exploit this. You're lucky you chose XOR
rather than addition -- I can't see a mod n attack here.
Looking a little more carefully:
* [1] and [6] are trivial linear transformations, which don't add any
security that I can see.
* Assuming that k is random, the probability that r2 is 0 in [4] is
2^{-5}. In this case, the rotate in [5] is a no-op, and the key,
which was mixed in [3], is removed again. Finally, the
complementation done in [1] is undone in [6]. The result of this is
that, with probability 2^{-5}, this entire transformation falls out
as being simply a key-dependent rotate.
* With probability 2^{-5} again, the rotate done in [3] is 0. Thus,
there's a 2^{-10} probability that the entire transformation is a
no-op.
With a key length of 32 bits, I can't see any attacks harder than brute
force against 16 rounds, except the certificational parity-leaking.
Then again, I've only looked at the cipher for a few minutes, and I'm
not the best cryptanalyst in the sci.crypt readership by a long way.
[snip]
P.S. Your C is awful.
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: OTP using BBS generator?
Date: 3 Aug 2000 16:51:50 GMT
lordcow77 <[EMAIL PROTECTED]> wrote:
> based on the computational equivalence of predicting BBS and deciding
> quadratic residuosity (and therefore factoring).
I don't mean to detract from your main point, with which I agree, but I
wasn't aware that it was proven that factoring can polytime reduce to
QRP. Can you provide a reference?
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (Mack)
Subject: Re: Small block ciphers
Date: 03 Aug 2000 17:09:43 GMT
>
>Mack wrote:
>>
>> >Mack wrote:
>> >
>> >> Mok-Kong.Shen wrote:
>> >> >We are doing at the bit level, aren't we? If one substitutes the known
>> >> >bits into the T terms, how can one say that an expression involving
>> >> >the T terms has T unknowns instead of B unknowns? (Compare
>> >> >my example quoted below.)
>> >> >
>> >>
>> >> Yes it is a bit level representation. The expression is developed before
>> >> we have known bits. Once those bits are known the expression can
>> >> be reduced. ie. without a known pair we develop the expression of
>> >> the cipher in ANF in terms of equations of output with input and
>> >> key being unknown. So we have T unknowns at this point. Once
>> >> we have a known pair we can reduce this to a set of equations in
>> >> K unknowns by substituting the known bits for the B variables.
>> >>
>> >> Now it is conceivable to develop a set of equations for K unknowns
>> >> by assuming a certain plaintext. This results in a chosen plaintext
>> >> attack rather than a known plaintext attack.
>> >
>> >Whether known-plaintext or chosen plaintext, the input bits are
>> >known. Hence I would say that in both cases we have B equations
>> >and K unknowns. Theoretically, with more plaintext and ciphertext
>> >pairs, the K unknowns can be solved. Practically, this could be
>> >a different issue. Anyway, I don't know whether useful and general
>> >assertiions could be made that are valid in all situations.
>>
>> In the final product we are solving the B equations in K unknowns.
>> In developing those equations we have to make a choice of whether
>> we are doing a known-plaintext attack in which case we need to
>> deal with B+K variables until we have the known plaintext to fill
>> in the inputs. Or we can pick a set of inputs and develop the equations
>> using those inputs in which case we never have to deal with the
>> B inputs as variables. If time is not an issue then we can
>> develop any known-plaintext into a set of equations.
>
>Perhaps I misunderstood. One has some complicated boolean
>expression as a function. This is purely formal. When we do
>the solution, we have from the known-plaintext the B input
>values. We substitute these in. The result can then be
>subjected to the solution process which tries to determine
>the value of the K variables. As far as I can see it doesn't
>differ from, say, the solution of a set of linear equations
>M*X = C. The values of the vector C are set in at solution
>time (dynamically) and then the elimination process, e.g.
>that of Gauss, begins. BTW, here the elements of C are
>never considered to be 'variables' in any sense, even though
>values have to be substituted into them before the solution
>process starts (before substitution they are of course unknown).
>So I surmise that probably we have essential terminological
>disparities.
>
>M. K. Shen
>
>
You have it exactly now. It is like a set of linear equations or
in this case non-linear equations. The attack can then be extended
to a probablistic attack by using approximations of the equations.
That way we don't have to deal with the really high order terms.
So we can produce an attack that works for a 128 bit block and
key.
Mack
Remove njunk123 from name to reply by e-mail
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: What is the word on TC5?
Date: 3 Aug 2000 17:13:24 GMT
tomstd <[EMAIL PROTECTED]> wrote:
> How does the generic attack work?
I described the impossible differentials in Feistel networks with
bijective F-functions in <[EMAIL PROTECTED]>. The
summary is that there are important structural differential properties
of Feistel networks with small numbers of rounds (3 for general Feistel
networks, 5 for networks with bijective F-functions).
Since the outer Feistel has only four rounds and a bijective F-function,
it exhibits such impossible differentials.
The impossible differential is (0, d) -/-> (?, d). Here's how it
evolves:
1. (0, d) ---> (d, 0)
2. (d, 0) ---> (d', d), with d' != 0
3. (d', d) ---> (d'', d'), with d'' != d
4. (d'', d') ---> (?, d'')
There's another, which is (d, 0) -/-> (d, 0), which is just the
five-round impossible differential without the first round.
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (Mack)
Subject: Re: OTP using BBS generator?
Date: 03 Aug 2000 17:20:05 GMT
>Mack <[EMAIL PROTECTED]> wrote:
>
>> >The key thing for me is finding out if there is a good reason why
>> >this isn't secure? There are proofs for BBS that prove it is as
>> >difficult as factoring whereas almost all other schemes (RSA etc)
>> >don't have a prove just a belief...
>>
>> The proofs that show BBS is as secure as factoring make a number of
>> assumptions. In this case it is that the discrete logarithm problem
>> is 'hard'. And that the quadratic residuosity problem is 'hard'. RSA
>> has proofs that follow from similar assumptions.
>
>Breaking the BBS is as hard as deciding quadratic residuosity. That's
>certainly no harder than factoring, because you can use factoring to
>decide quadratic residuosity, and indeed this is the only way we know
>for doing this. The quadratic residuosity problem (QRP) is old and
>well-known; however, we don't know that it's actually as dificult as
>factoring.
>
>By contrast, we know that breaking RSA is as difficult as solving the
>RSA problem (RSAP). This isn't helpful -- it's just a restatement of
>the same thing. We've no idea whether RSAP is actually difficult.
>Again, the only way we know for solving the general RSAP is to factor.
>On the other hand, RSAP is new.
>
>> The BBS and RSA are very similar. BBS requires that the primes
>> be of special form. RSA is a bit more liberal
>
>The form for a Blum modulus isn't very special: the primes p and q must
>each be congruent to 3 (mod 4); i.e., the bottom two bits of each should
>be set. The other stuff with (p - 1)/2 being prime and so on isn't
>particularly important unless you don't understand the security warranty
>on the BBS generator.
>
>> although for longest period they should probably be of the same form.
>
>Can you justify this statement? I can't offhand see why an RSA modulus
>would need to be a Blum integer for this.
>
The period of the RSA generator should be findable using the same method
as BBS. I don't have a proof of period but it can't really hurt can it?
>> BBS is a bit more efficient than the RSA generator (one
>> multiplication).
>
>One squaring, in fact. Squaring is faster than multiplication.
>
No, one multiplication. BBS uses one squaring. RSA uses one
squaring and one multiplication.
>-- [mdw]
>
Mack
Remove njunk123 from name to reply by e-mail
------------------------------
Subject: Re: OTP using BBS generator?
From: lordcow77 <[EMAIL PROTECTED]>
Date: Thu, 03 Aug 2000 10:27:22 -0700
[EMAIL PROTECTED] (Mark Wooding) wrote:
>lordcow77 <[EMAIL PROTECTED]> wrote:
>
>I don't mean to detract from your main point, with which I
agree, but I
>wasn't aware that it was proven that factoring can polytime
reduce to
>QRP. Can you provide a reference?
>
A proof would be a surprise to me as well :-) QRP polytime
reduces to IFP, although I haven't seen anything proven on a
polytime reduction from IFP to QRP.
===========================================================
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: OTP using BBS generator?
Reply-To: [EMAIL PROTECTED]
Date: Thu, 3 Aug 2000 17:31:19 GMT
Grant Anderson <[EMAIL PROTECTED]> wrote:
: The key thing for me is finding out if there is a good reason why this
: isn't secure? There are proofs for BBS that prove it is as difficult as
: factoring whereas almost all other schemes (RSA etc) don't have a prove
Being hard to predict is a different thing to being /impossible/
to predict - which is what an ideal OTP ought to be.
For example an attacker can guess a BBS seed. If they get it right,
reams of plausible plaintext will spew out - while if they don't it is
/extremely/ unlikely to. This attack is impossible with a real OTP.
If you use PRNG output and call the resulting system an OTP, people will
not think you're serious.
Also, being "as hard as factoring" may not say very much in security terms.
QC advocates seem to think factoring is about to turn out to be
"not as hard as had previously been thought".
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ VIPAR GAMMA GUPPY.
------------------------------
From: "Paul Morris" <[EMAIL PROTECTED]>
Subject: Cracking RC4-40 in FPGA hardware
Date: Thu, 3 Aug 2000 18:53:06 +0100
Having recently posted an article called 'Hardware based PK device' I was
amazed by the very positive response I received - thank you for your time.
Anyway, I received a mail from Paul Rubin who suggested building a device
capable of cracking RC4-40. Since I think cracking a code has more 'wow
factor' for project markers (and a more tangible goal) I thought I would
investigate this a little further especially since being in the UK I think
40 bits is all we can legally import from the US.
Paul mentioned that RC4-40 is used in exportable web browsers (presumably as
part of the SSLv3) and for password protected files in Microsoft Word.
Although RSA's site states that RC4 is considered strong, Paul mentioned
that it could be broken in 'a few months' with a PIII. Given that RSA
consider it strong are there any other high profile uses for RC4-40? I'm
very much looking for some 'wow factor' here!
Fundamentally, Paul suggested that multiple (cheap) FPGAs, running multiple
threads each, could potentially brute-force break an RC4-40 in, say, 200
hours or less. Paul coined the name 'Shallow Crack' in reference to the EFF
Deep Crack machine. Does anybody have any comments on the feasibility of
this? Given my limited (but burgeoning) understanding of crypto I would
assume that a brute-force attack like this would require the attacker to
have both ciphertext and plaintext. If this is the case it makes a
transaction using RC4-40, where the key used is a session key, impossible to
break since even if one message is compromised the next transmission will
use a different key. Or am I on the wrong track?
I would be very grateful if I could get (yet more) generous help from those
in the know.
a, Is the idea outlined above a feasible concept for a 9 month project?
b, Is there a similar yet much easier counterpart algorithm that could prove
the feasability of the idea (and give me some progress mile stone) along the
way?
c, If I don't have both ciphertext and plaintext how can a brute-force crack
work?
d, Anything else you can think of???
When I finish reading the RSA faq I should be a bit further along
understanding modern crypto but there is no substitute for experience so I
would love to here your comments. Anything you can contribute will be
gratefully received.
Cheers
Paul Morris
[EMAIL PROTECTED]
------------------------------
From: "Andreas Sewe" <[EMAIL PROTECTED]>
Subject: Re: IV for arfour
Date: Thu, 3 Aug 2000 19:53:46 +0200
"David A. Wagner" wrote:
> I see. Ok, no confusion left. Thanks.
Ok, I'm sorry for any confusion or diffusion or wathsoever caused by
my posting.
And thanks for your patience with me and this thread.
> I have to admit the proposal doesn't seem terribly practical to me.
> Many folks complain about 8 or 16 bytes of overhead per packet for a
> crypto IV; I can't imagine what they'd say if I asked for 256 bytes. :-/
> But I guess there are probably some applications where the overhead is
> acceptable. (encryption of very large files, maybe?)
Very large files, exactly - you don't have to worry about bandwidth and
overheads there. I'd say yes, if 256 bytes are asked for this application.
Andreas Sewe
------------------------------
From: Tom Anderson <[EMAIL PROTECTED]>
Subject: Re: JavaCard vs Multos security
Date: Thu, 3 Aug 2000 18:59:53 +0100
On 31 Jul 2000, Shawn Willden wrote:
> Daniel James <[EMAIL PROTECTED]> writes:
>
> > In article <8ls68p$hr2$[EMAIL PROTECTED]>, wrote:
> >
> > > I am somehwat surprised that Multos has so much to offer with only
> > > an 8 bit cpu...the new javacard cpu's are 32 bit risc, and that
> > > has considerable more power to run all the Java bytecode...
>
> All the Java bytecode? I'm not sure what you mean by that, but my
> first take is: not likely. The Java libraries are so huge that any
> card-based VM is going to have to be stripped down for the foreseeable
> future.
this is what's called the 'Java 2 Micro Edition':
http://java.sun.com/j2me/
it's still pretty chunky, though: 128 kB for the JVM and libraries, and it
wants a 16-bit chip at the minimum.
tom
------------------------------
From: Mike Rosing <[EMAIL PROTECTED]>
Subject: Re: Elliptic Curves encryption
Date: Thu, 03 Aug 2000 12:55:23 -0500
Roger Schlafly wrote:
>
> Doug Kuhlman wrote:
> > Have you seen a proof that breaking ECDH is equivalent to the
> > ECDLP? I haven't.
>
> No. It is an open question.
Well, I guess I need to see what's open about it. ECDH is just
Alice sends aP to Bob
Bob sends bP to Alice
they both compute the secret abP.
ECDLP is finding a (or b) from aP (or bP) and P. Once you have a or b,
you have the secret.
If you mean whether f(aP, bP) = abP is a possible function without
solving ECDLP is simpler than ECDLP, then I suppose it's an open
question. But I don't see how. Every point can be constructed in
multiple ways from P. Finding f() seems harder to me than ECDLP,
but I've got a lot of math to learn yet :-)
Patience, persistence, truth,
Dr. mike
------------------------------
From: Mike Rosing <[EMAIL PROTECTED]>
Subject: Re: Pegwit - "Weak" ECC with GF(2^m), m composite?
Date: Thu, 03 Aug 2000 12:59:14 -0500
Frank M. Siegert wrote:
> So, are there plans to change Pegwit to make it secure...?
Talk with George, I'm sure he'd appreciate some help!
::Send mail to George at [EMAIL PROTECTED]
Patience, persistence, truth,
Dr. mike
------------------------------
From: [EMAIL PROTECTED] (John Hascall)
Subject: Re: microwave cd
Date: 3 Aug 2000 17:55:22 GMT
Steve Rush <[EMAIL PROTECTED]> wrote:
>>Probably the most convenient and effective thing to do, especially if
>>you have a lot of CD's to destroy, is take them to the city dump and
>>toss them into a high temperature incinerator.
>Are there any municipal garbage incenerators still operating in the USA? I
>thought the EPA banned them years ago. Throw something in the garbage now,
>and it goes into a landfill.
Yes, in Ames, Iowa, we turn our garbage into electricity:
http://www.city.ames.ia.us/worksweb/resource%20recovery/resrec.html
(however, unless it was previously physically reduced to small
enough pieces that the blower would separate it like paper, it
would go to the landfill rather than being burned).
John
--
John Hascall (__) Shut up, be happy.
Software Engineer, ,------(oo) The conveniences you demanded
Acropolis Project Manager, / |Moo U|\/ are now mandatory.
ISU Academic IT * ||----|| -- Jello Biafra
------------------------------
** 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
******************************
