Cryptography-Digest Digest #102, Volume #12 Sun, 25 Jun 00 10:13:01 EDT
Contents:
Idea with SHA (tomstd)
Re: Algo's with no easy attacks? ("Douglas A. Gwyn")
Re: Quantum computing ("Douglas A. Gwyn")
Attacking TC5a (tomstd)
Re: software protection schemes (lament)
Re: Quantum computing (Dido Sevilla)
Re: software protection schemes (tomstd)
Re: Quantum computing (Roger Schlafly)
Re: Attacking TC5a (tomstd)
Re: Quantum computing ("Douglas A. Gwyn")
Re: Linear Feedback Shift Register *with* lock-up? (Nick Maclaren)
Re: Linear Feedback Shift Register *with* lock-up? (David Blackman)
DES 64 bit OFB test vectors (Jack Spencer)
Re: Weight of Digital Signatures ("Lyalc")
Re: Compression and known plaintext in brute force analysis (restatements caused by
the missing info .... thread) (Tim Tyler)
Announce: Catacomb 2.0.0pre2 now available (Mark Wooding)
Re: DES 64 bit OFB test vectors (Mark Wooding)
Re: software protection schemes ("Thomas J. Boschloo")
----------------------------------------------------------------------------
Subject: Idea with SHA
From: tomstd <[EMAIL PROTECTED]>
Date: Sat, 24 Jun 2000 19:57:51 -0700
Just out of "la bleu" I was thinking (yes a shocker for me too)
what if you took the W[] expansion from SHA and turned those
into round keys... then wouldn't you have a 160-bit block
cipher? I am not looking at the specs right now... but from
what I can gather it should be invertable :)
My two cents.
Tom
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Algo's with no easy attacks?
Date: Sun, 25 Jun 2000 04:11:56 GMT
Simon Johnson wrote:
> Really, i can only invisige that the One Time Pad is the only
> attack-less cipher out there.
Without getting into specifics, if the key changes before enough
information can be extracted from the ciphertext, then a system
can be secure under the normal model for cryptanalytic attack.
Certainly, less key than the full amount of plaintext can be used
without giving the cryptanalyst any opportunity. However, in
practice in high-volume cryptosystems, sooner or later something
goes wrong and an entering wedge can be found.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Quantum computing
Date: Sun, 25 Jun 2000 04:15:47 GMT
[EMAIL PROTECTED] wrote:
> What will come first a quantum computer or a proof that P != NP?
We *know* what is involved in building quantum computers,
and many people are in fact working on building them.
We do *not* know what would be involved in a successful
proof of P?=NP.
------------------------------
Subject: Attacking TC5a
From: tomstd <[EMAIL PROTECTED]>
Date: Sat, 24 Jun 2000 21:48:39 -0700
Using "addition modulo 256" as a notion of difference (should I
have used subtraction?) The best 8-round differential I found on
the 16-bit Feistel is the following
p = 10298, 6d -> 37 -> 2e -> b7 -> 72 -> 8e -> f3 -> 10
Where p/256 is the log2(prob). i.e in this case it's 2^40 which
means it's not usefull.
I dunno if I should have used addition... Using subtraction I get
p = 11133, 26 -> 58 -> 09 -> e7 -> cb -> a3 -> af -> da
Which is still not applicable, even on three rounds using
subtraction as a difference I get
p = 2715, 86 -> c7 -> 55
Which is still not applicable.
Any ideas?
Tom
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
From: lament <[EMAIL PROTECTED]>
Subject: Re: software protection schemes
Date: Sun, 25 Jun 2000 05:07:43 GMT
In article <g4u35.30$[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
> Almost any software protection scheme running on the PC suffers from this
> same vulnerability. If the attacker finds the magic bit that finally
> authenticates the user, the software protection will not work.
Big "If."
> Usually it
> is very easy to find this bit. If there are multiple levels of checks with
> many bits scattered throughout the executable, the job is a little more
> difficult.
Given that billions of instructions transpire, how do you know which one(s) are the
one?
> Any scheme that is deliberately and perversely complex is likely
> to be buggy and slow and still subject to attack by automated tools. Dongle
> protection scheme fall into this category.
"...deliberately and perversely complex" seems to be a necessary condition of
encryption. Is all encryption code "buggy and slow"? You say "still subject to attack
by automated tools" but you don't say how.
> Most dongle protection scheme
> have been broken.
The CAD industry uses dongles.
> Good, reliable software protection in the PC environment is a myth.
I guess this depends on what you mean by "good," "reliable" and "a myth."
------------------------------
From: Dido Sevilla <[EMAIL PROTECTED]>
Subject: Re: Quantum computing
Date: Sun, 25 Jun 2000 13:01:19 +0800
[EMAIL PROTECTED] wrote:
>
> What will come first a quantum computer or a proof that P != NP? Does
> anyone want to bet?
>
Quantum computers already exist, and they *work*. The only trouble with
them is that all presently known approaches (bulk spin resonance systems
and ion traps for example), have been difficult to generalize to the
arbitrarily large numbers of qubits needed for practical work. They're
enough to pedagogically demonstrate some ideas of quantum computers, as
well as simulate some simple quantum phenomena, but not enough to factor
a big number using Shor's algorithm...
--
Rafael R. Sevilla <[EMAIL PROTECTED]> +63 (2) 4342217
ICSM-F Development Team +63 (917) 4458925
University of the Philippines Diliman
------------------------------
Subject: Re: software protection schemes
From: tomstd <[EMAIL PROTECTED]>
Date: Sat, 24 Jun 2000 22:12:05 -0700
lament <[EMAIL PROTECTED]> wrote:
>In article <g4u35.30$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] says...
>
>> Almost any software protection scheme running on the PC
suffers from this
>> same vulnerability. If the attacker finds the magic bit that
finally
>> authenticates the user, the software protection will not
work.
>
>Big "If."
>
>> Usually it
>> is very easy to find this bit. If there are multiple levels
of checks with
>> many bits scattered throughout the executable, the job is a
little more
>> difficult.
>
>Given that billions of instructions transpire, how do you know
which one(s) are the
>one?
By single stepping the code :)
>> Any scheme that is deliberately and perversely complex is
likely
>> to be buggy and slow and still subject to attack by automated
tools. Dongle
>> protection scheme fall into this category.
>
>"...deliberately and perversely complex" seems to be a
necessary condition of
>encryption. Is all encryption code "buggy and slow"? You
say "still subject to attack
>by automated tools" but you don't say how.
>
I beg to differ. Not all cryptography is buggy and slow. Alot
of good tools put the trust into the randomness of the
parameters generated.
>> Most dongle protection scheme
>> have been broken.
>
>The CAD industry uses dongles.
They are not cryptographers I am sorry to report.
>> Good, reliable software protection in the PC environment is a
myth.
>
>I guess this depends on what you mean by "good," "reliable"
and "a myth."
Hey if your method stops you from losing 100G then that's
great. But don't stop and think it must stop everyone!
Tom
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
From: Roger Schlafly <[EMAIL PROTECTED]>
Subject: Re: Quantum computing
Date: Sat, 24 Jun 2000 22:24:13 -0700
Dido Sevilla wrote:
> enough to pedagogically demonstrate some ideas of quantum computers, as
> well as simulate some simple quantum phenomena, but not enough to factor
> a big number using Shor's algorithm...
That's all they are. They demo some quantum ideas, but do not
compute anything. Cannot even factor 4=2x2.
Maybe I'm in the minority, but I don't think we'll see any
quantum computers without some big theoretical and technological
breakthroughs.
------------------------------
Subject: Re: Attacking TC5a
From: tomstd <[EMAIL PROTECTED]>
Date: Sat, 24 Jun 2000 22:22:04 -0700
It seems addition is the best measure of difference in TC5a. My
best diff attack only attacks four rounds or less of the 16-bit
Feistel. It seems five rounds is marginally secure (2^-20) and
eight rounds is really secure (the best eight round diff has a
prob of 2^-38).
In TC5a attacking the smaller feistels is a good place to start
right?
Any insight would be nice :)
Tom
--
TC5a is on my website
http://www.geocities.com/tomstdenis/
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Quantum computing
Date: Sun, 25 Jun 2000 06:07:12 GMT
Roger Schlafly wrote:
> Maybe I'm in the minority, but I don't think we'll see any
> quantum computers without some big theoretical and technological
> breakthroughs.
There is a kind of "critical mass" that will occur when enough
error correction can be accrued along with the noisy qubits.
------------------------------
From: [EMAIL PROTECTED] (Nick Maclaren)
Crossposted-To: comp.theory,sci.math
Subject: Re: Linear Feedback Shift Register *with* lock-up?
Date: 25 Jun 2000 07:05:16 GMT
In article <8itftv$rdd$[EMAIL PROTECTED]>,
David A. Wagner <[EMAIL PROTECTED]> wrote:
>In article <8iocit$1ghu$[EMAIL PROTECTED]>,
>Ponder <[EMAIL PROTECTED]> wrote:
>> Also, is there a good algorithm for converting the elements of
>> an LFSR sequence into the actual value of the count?
>
>Yes, it's ``just'' the discrete log problem in GF(2^N), and subexponential
>algorithms are known.
Can you clarify what you mean by subexponential in this context?
It is a horribly ambiguous term :-(
Regards,
Nick Maclaren,
University of Cambridge Computing Service,
New Museums Site, Pembroke Street, Cambridge CB2 3QG, England.
Email: [EMAIL PROTECTED]
Tel.: +44 1223 334761 Fax: +44 1223 334679
------------------------------
From: David Blackman <[EMAIL PROTECTED]>
Subject: Re: Linear Feedback Shift Register *with* lock-up?
Date: Sun, 25 Jun 2000 17:51:10 +1000
Nick Maclaren wrote:
>
> In article <8itftv$rdd$[EMAIL PROTECTED]>,
> David A. Wagner <[EMAIL PROTECTED]> wrote:
> >In article <8iocit$1ghu$[EMAIL PROTECTED]>,
> >Ponder <[EMAIL PROTECTED]> wrote:
> >> Also, is there a good algorithm for converting the elements of
> >> an LFSR sequence into the actual value of the count?
> >
> >Yes, it's ``just'' the discrete log problem in GF(2^N), and subexponential
> >algorithms are known.
>
> Can you clarify what you mean by subexponential in this context?
> It is a horribly ambiguous term :-(
>
> Regards,
> Nick Maclaren,
> University of Cambridge Computing Service,
> New Museums Site, Pembroke Street, Cambridge CB2 3QG, England.
> Email: [EMAIL PROTECTED]
> Tel.: +44 1223 334761 Fax: +44 1223 334679
If you can make the Number Field Sieve, or the Multiple Polynomial
Quadratic Sieve, work for GF(2^N), then the running time of those would
be less than O(A^N) for any A greater than 1. This is less than
exponential in N. I rather suspect you can make those algorithms work
for GF(2^N), but i don't know for sure. (However these methods are still
worse than any polynomial. They are also quite memory hungry. I expect
the upper limit for N would be somewhere in the range 300 to 600 with
current hardware.)
Otherwise you would have to fall back on the trusty old Pollard Rho (or
maybe Pollard Lambda). Both of those are exponential time in N, but not
too bad. You could hope to attack N=80 and maybe even N=100, if you had
patience and a really fast modern computer.
------------------------------
From: Jack Spencer <[EMAIL PROTECTED]>
Subject: DES 64 bit OFB test vectors
Date: Sun, 25 Jun 2000 19:42:28 +1000
Hi,
I need some test vectors for DES 64 bit OFB mode.
I already have a tested DES module so OFB implementation
is trivial. Still, it's better if I have some independent vectors.
I serched the web but I only found some stale links and
useless information.
Please post the information here if you can help.
Thanks,
JS
------------------------------
From: "Lyalc" <[EMAIL PROTECTED]>
Subject: Re: Weight of Digital Signatures
Date: Sun, 25 Jun 2000 21:14:07 +1000
I know we are close to discussing legal issues, but
the motive behind the signing is important (e.g. coercion repudiates an
otherwise genuine signature). Electronically, we can't really detect or
cater to these sorts of situations - yet.
One day, the rule makers will decide how to handle these ambiguous
situations.
In the meantime, we all play elelctronic signatures "by ear"
Lyal
Robert Stonehouse wrote in message
<[EMAIL PROTECTED]>...
>Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>>Robert Stonehouse wrote:
>>> [EMAIL PROTECTED] (John Savard) wrote:
>>> ...
>>> >A law that makes a digital signature "just as binding as one in ink",
>>> >when it is so much easier to break into someone's house and read their
>>> >hard drive than forge their signature perfectly makes ordinary people
>>> >much more vulnerable to forgery than before.
>>> ...
>>> The thing that makes an ink signature binding is the fact that it
>>> was written by the right person. If your bank pays out on a forged
>>> cheque, saying 'Well, it was a perfect forgery' won't help the bank
>>> at all. The bank has to make it good to you.
>>>
>>> It is hard to imagine how any law authorising digital signatures can
>>> preserve that protection for bank customers and others who sign
>>> documents.
>>
>>But a cheque forgery has to be ascertained by experts who have to
>>use judgements and, I believe, don't always have 'absolute' certainty.
>>So I guess that some parallel mechanism could function.
>
>Not necessarily. There can be other ways of showing you didn't sign
>the document apart from an examination of the document. What matters
>is whether you signed it or not.
>
>The terms of electronic transactions mostly say that, if the bank
>gets a transaction that satisfies the conditions, it can pay. That
>is, the electronic details are final.
>[EMAIL PROTECTED]
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Compression and known plaintext in brute force analysis (restatements
caused by the missing info .... thread)
Reply-To: [EMAIL PROTECTED]
Date: Sun, 25 Jun 2000 10:25:23 GMT
James Felling <[EMAIL PROTECTED]> wrote:
: Joseph Ashwood wrote:
:> [...] with compression a slightly different result can occur, we can end up
:> with a deflation down to significantly smaller sizes. A quick test with
:> winzip on a large text file gave a size reduction of 65%, more usefully for
:> this that means that the compression resulted in 3 bytes per byte. Moving
:> outward this leads to 3 blocks per block, so with a (semi)known plaintext,
:> under compression, it is entirely possible that the unicity distance could
:> actually be reduced.
: Ok, I think I see what you are claiming. That given n encrypted blocks and a
: plaintext of known character, with compression you may actually need fewer
: cyphertext blocks than without compression. I belive this to be a possible
: condition to occur. OTOH I believe you are missing something here.
: Given we have a plaintext P composed of blocks p(i), and after compression
: we have a compressed plaintext C composed of blocks c(i). It may be
: possible to recognise the code with fewer c(i)'s , however it would still
: require more p(i) blocks.
I wondered if this was what was intended.
However, it still doesn't seem to make any sense.
If the compressor actually compresses, then a larger proportion of
cyphertexts will result in expansion to valid plaintexts (for any given
length of cyphertext) - so you'll typically need a larger cyphertext (as
well as a larger original plaintext) to reduce the number of possible
plaintexts to 1.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Niagra falls.
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Announce: Catacomb 2.0.0pre2 now available
Date: 25 Jun 2000 13:24:04 GMT
I've sent out another prerelease of my Catacomb cryptographic library.
The new version has a slightly different interface to secret sharing,
and has an important bug fix in the multiprecision division routine.
Visit http://www.excessus.demon.co.uk/misc-hacks/#catacomb for more
information, or to download a copy.
Catacomb is free software, distributed under the terms of the GNU
Library General Public License.
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: DES 64 bit OFB test vectors
Date: 25 Jun 2000 13:28:24 GMT
Jack Spencer <[EMAIL PROTECTED]> wrote:
> Hi,
>
> I need some test vectors for DES 64 bit OFB mode.
> I already have a tested DES module so OFB implementation
> is trivial. Still, it's better if I have some independent vectors.
>
> I serched the web but I only found some stale links and
> useless information.
>
> Please post the information here if you can help.
I don't have any to hand, but maybe this will help:
key 0123456789abcdef
IV 0f1e2d3c4b5a6978
First 256 bytes of output are
00000000 : f9 dd 49 8a f8 84 a9 7f 5a 55 d6 a9 2e 6f 03 3a : ..I.....ZU...o.:
00000010 : 76 f8 72 c3 53 12 bd ce 9b 62 85 1e 9b bd ee b8 : v.r.S....b......
00000020 : 5b 87 bf 1e d7 93 f5 80 e7 d5 08 26 71 b5 3e ce : [..........&q.>.
00000030 : 07 1c c9 5e cb 31 68 ff 21 05 d9 77 a8 80 25 f5 : ...^.1h.!..w..%.
00000040 : ff d9 8d a4 52 85 c9 99 5c a2 c3 74 de ce a4 27 : ....R...\..t...'
00000050 : 5c 80 02 ca 49 0b e2 1e 6b 33 0a fc 5c 35 22 a9 : \...I...k3..\5".
00000060 : 53 68 0b 18 1d dd ed 35 fe de 4b 5e 07 2f 10 f1 : Sh.....5..K^./..
00000070 : 6a bf 14 49 11 1e 55 6e 28 2c 0d 68 89 1c 84 f1 : j..I..Un(,.h....
00000080 : c6 3b 29 56 1e 54 a9 10 ea a0 77 7c 9b dd eb e8 : .;)V.T....w|....
00000090 : 73 e4 f6 c5 2d 82 1b 00 8c 6d 49 3b e2 92 58 e9 : s...-....mI;..X.
000000a0 : d2 67 45 ed c3 ef 89 8e 13 f3 42 0a 5c 73 21 bd : .gE.......B.\s!.
000000b0 : 6c 8e ef 92 f2 7f 7b da 07 38 ca 61 af d3 74 15 : l.....{..8.a..t.
000000c0 : 6b 97 a3 da 79 4e 9b 8f b4 41 f1 0b 49 e5 e0 3a : k...yN...A..I..:
000000d0 : e5 56 e7 c6 29 1f 8a 3d 5f 90 45 fb f9 67 c2 6e : .V..)..=_.E..g.n
000000e0 : 68 46 05 6d a2 7f 2d a4 86 fd 0b 9f 07 1e 01 45 : hF.m..-........E
000000f0 : 8c f6 5e 0b 8e 1a 04 ad 90 84 ba 92 c5 4d e7 70 : ..^..........M.p
(Everything is big-endian.)
-- [mdw]
------------------------------
From: "Thomas J. Boschloo" <[EMAIL PROTECTED]>
Subject: Re: software protection schemes
Date: Sun, 25 Jun 2000 15:57:33 +0200
lament wrote:
>
> In article <g4u35.30$[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
>
> > Almost any software protection scheme running on the PC suffers from this
> > same vulnerability. If the attacker finds the magic bit that finally
> > authenticates the user, the software protection will not work.
>
> Big "If."
>
> > Usually it
> > is very easy to find this bit. If there are multiple levels of checks with
> > many bits scattered throughout the executable, the job is a little more
> > difficult.
>
> Given that billions of instructions transpire, how do you know which one(s) are the
> one?
I have broken a few copy protection schemes in the DOS era and if there
is some input required from the user, you just break there and go up a
few subroutines to see what changes when you enter the correct data and
what happens when you don't. You can easily do a few core dumps and find
the data that always changes, as oposed to data that changes even when
you don't proceed to the user input. Then, with modern debuggers, it is
easy to set a trap on that data and see where it gets accessed. These
are the points where you modify the code.
One word of advice, don't do any system calls in your copy protection
code! I have broken all to many protections where I could just listen to
the system calls, wait for the right moment and change the code, set a
breakpoint, change some code there again and restore everything before
the copy protection code is verified later.
Dongles are even easier. You can trap the code that tries to access
them. Same with cd-rom protections or the old floppy disk protections.
You just wait for that weird interrupt, hack the code and pass the
proper values. Breaking the hardware inside the dongle is the hardest.
This because you have to replace it with a software equivalence.
Anyways, have fun.
If the product does not suck anyways, it will be broken.
Hi!
--
We live in the Matrix <http://www.whatisthematrix.com>
http://wwwkeys.pgp.net:11371/pks/lookup?op=get&search=0x225CA009
Email: boschloo_at_multiweb_dot_nl
------------------------------
** 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
******************************
