Cryptography-Digest Digest #976, Volume #11 Thu, 8 Jun 00 13:13:01 EDT
Contents:
Re: equation involving xor and mod 2^32 operations (tomstd)
Re: testing non linearity of arithmetic-logic combinations (Terry Ritter)
Re: testing non linearity of arithmetic-logic combinations (tomstd)
Re: questions on TEA (Simon Johnson)
Re: testing non linearity of arithmetic-logic combinations (Terry Ritter)
Re: Brute forcing for Counterpane's Password Safe ("John E. Kuslich")
Re: software protection schemes (Joseph Reuter)
Re: Arithmetic Coding (SCOTT19U.ZIP_GUY)
Re: questions on TEA (Andru Luvisi)
Digital Certificates ("IanM")
Re: DES question (Mark Wooding)
Random IV Generation (Charles)
Re: DES question (Mark Wooding)
Re: Brute forcing for Counterpane's Password Safe ("Joseph Smith")
Re: software protection schemes (Mike Rosing)
----------------------------------------------------------------------------
Subject: Re: equation involving xor and mod 2^32 operations
From: tomstd <[EMAIL PROTECTED]>
Date: Thu, 08 Jun 2000 09:04:39 -0700
In article <8hofe5$3sh$[EMAIL PROTECTED]>, Simon Johnson
<[EMAIL PROTECTED]> wrote:
>In article <8hnbrp$1av$[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] (David A. Wagner) wrote:
>> In article <[EMAIL PROTECTED]>,
>> Anton Stiglic <[EMAIL PROTECTED]> wrote:
>> [ Solve (a+x) xor (b+x) = c for x; a,b,c are known. ]
>>
>> Work bit-by-bit, starting with the least significant bit of x
>> and working your way up. Once you know (all possibilities
for)
>> the low n bits of x, you can try extending each of them with a
>> 0 bit and a 1 bit in the n+1-th position, and checking whether
>> the equation holds mod 2^{n+1} to filter out the wrong ones.
>> Cook until done.
>>
>I know Addition and Xor don't commute (exactly what that means
i would
>like to know.). Is this statement relavent to this problem?
Commute means (I think) that you can rearrange the equation and
get the same result. For example
eq1: a + b + c = 4
is equivelant to
eq2: b + a + c - 4 = 0
In the terms of XOR it doesn't work because
eq3: a + (b xor c) = 4
is not the same as
eq4: b + (a xor c) - 4 = 0
Tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: testing non linearity of arithmetic-logic combinations
Date: Thu, 08 Jun 2000 16:06:41 GMT
On Thu, 08 Jun 2000 05:13:43 GMT, in <[EMAIL PROTECTED]>, in
sci.crypt "Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote:
>In addition to what was said in other responses,
>"linearity" can be reasonably defined in more than one
>(nonequivalent) way.
>The other respondents seem to be assuming the usual operations
>in GF(2), which is probably the most reasonable choice.
Certainly there are various forms of linearity, but as far as I know,
"nonlinearity" is generally understood in open cryptography to be
short for "Boolean function nonlinearity," if only because we don't
have any other sort of good nonlinearity measure.
>In that context, if you want a maximum degree of nonlinearity
>you probably want what is called a "bent function".
>I suspect a Web search would find a few papers on the topic.
Unfortunately, bent functions are always unbalanced, which is
completely unacceptable. See, for example:
http://www.io.com/~ritter/GLOSSARY.HTM#BentFunction
Another problem is that while there are various different
constructions for bent functions, most produce a different proper
subset of the universe of all possible bent functions, which raises
both keying and attack issues for each particular construction.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
Subject: Re: testing non linearity of arithmetic-logic combinations
From: tomstd <[EMAIL PROTECTED]>
Date: Thu, 08 Jun 2000 09:07:24 -0700
In article <[EMAIL PROTECTED]>, Tim Tyler <[EMAIL PROTECTED]>
wrote:
>cranky cransky <[EMAIL PROTECTED]> wrote:
>: Terry Ritter <[EMAIL PROTECTED]> wrote in message
>
>:> Articles have been published on this, but no arithmetic-
level function
>:> is very nonlinear. [...]
>
>: my idea was to test the relative non linearity (if those
words can be
>: used ) of various combinations of simple chip level
operations ( << , >> ,
>: xor, and, bit-complement, +, - ...etc )on 32 and 64 bit ints,
in an effort
>: to make systematic the process of choosing functions for the
simulation of
>: 32 bit or 64 bit substitution table. rather than just
randonly combining a
>: few.
>
>Of those you mention only + and - have any non-linearity at all.
>
>AND and OR are normally considered non-linear operations, but
destroy
>information and do not immediately offer invertability.
This is not true. Consider the following
a' = (a and c) or (b and ~c)
b' = (b and c) or (a and ~c)
Which is completely invertable, not terribly usefull, but
invertable.
>Feistel constructs allow their use - and there are other
approaches to
>preserving invertability while using non-linear operations.
>
>: so my aim is to discover the most nonlinear combination of
operands for
>: mixing, that creates the greatest avalanche (perhaps
avalanche is not a
>: function of non linearity, i dont know).
>
>In many block cyphers, linear XOR-style operations are often
those used
>to promote avalanche. If avalanche is diffusion, non-linearity
is
>confusion.
Xor's can be used to promote non-linearly consider sboxes with
characteristic of 2 such as x^3 mod p, where p is a polynomial
in GF(2^n) (n is odd).
Tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: Simon Johnson <[EMAIL PROTECTED]>
Subject: Re: questions on TEA
Date: Thu, 08 Jun 2000 16:00:22 GMT
In article <[EMAIL PROTECTED]>,
Dave Hazelwood <[EMAIL PROTECTED]> wrote:
> Yup the original TEA was found to have weaknesses and thus gave birth
> to XTEA. I forget the details though but it was all here in this group
> so try searching dejanews.
>
> Dido Sevilla <[EMAIL PROTECTED]> wrote:
>
> >
> >This post has to do with the Tiny Encryption Algorithm (TEA)
described
> >by Wheeler and Needham (http://www.cl.cam.ac.uk/ftp/users/djw3/tea.ps
> >and http://www.cl.cam.uk/ftp/users/djw3/xtea.ps). Has anyone tried
to
> >use this block cipher? From what I see, the algorithm is really
quite
> >simple and looks pretty easy to code, even in most forms of assembly
> >language. It doesn't go through quite as many contortions as the
more
> >sophisticated algorithms do, but it runs a fairly simple core
through a
> >lot of rounds (32 to be exact). Does it have any weaknesses which
the
> >authors have not described in their papers yet?
>
>
I believe it was a weekness in the key-shedule... Exactly what changes
where made in XTEA, i don't know.
However, XDES was a version of Whitened version of des. For this reason
i have a feeling XTEA is a Whitened version of TEA.
--
Hi, i'm the signuture virus,
help me spread by copying me into Signiture File
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: testing non linearity of arithmetic-logic combinations
Date: Thu, 08 Jun 2000 16:12:01 GMT
On Thu, 08 Jun 2000 11:24:17 +0200, in
<[EMAIL PROTECTED]>, in sci.crypt Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
>'a random table ... is unlikely to be invertible' seems to suggest in
>the present context that a Latin square is invertible. In which sense
>is that? Since Latin square is used, as you said, as a 2-in 1-out function,
>
>it could by nature not be invertible, i.e. one can't from the output
>compute the input, if I don't err. Thanks in advance.
The exact same issue occurs with XOR, also a dyadic operation, yet we
still manage to think of that as invertible. See the example:
http://www.io.com/~ritter/GLOSSARY.HTM#LatinSquareCombiner
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: "John E. Kuslich" <[EMAIL PROTECTED]>
Subject: Re: Brute forcing for Counterpane's Password Safe
Date: Thu, 8 Jun 2000 09:15:07 -0700
It is unlikely that anything other than a brute force attack would be
successful in such a quality product (although it is possible). In light of
this fact, time would be better spent recovering the passwords from the
target QuickBooks, Quicken, Excel, WordPerfect etc. files. Most commercial
software still suffers from the EAR hangover imposed by the pointy headed
geeks in our federal government and therefore uses very weak encryption.
Those that use good encryption can be attacked by simple bypass techniques.
Password recovery software abounds on the Internet. For a few dollars most
of the important financial and word processor passwords could be recovered
in a few minutes.
I will refrain from recommending a source of password recovery software.
They are all available by searching the Net :--)
JK Password Recovery Software http://www.crak.com
Joeseph Smith <[EMAIL PROTECTED]> wrote in message
news:rab%4.30$[EMAIL PROTECTED]...
> I've been asked to help the executor of the estate
> of a fellow who recently died in Florida. The fellow
> was techno-savvy enough to use Password Safe
> from Counterpane to hold his various account names
> and passwords. Unfortunately, he was not real-world
> savvy enough to leave a way for his heirs to recover
> the data. The executor has tried various obvious
> passwords (names of grandchildren, significant dates
> and places, etc.), but they have not worked.
>
> Does anyone have a program that does brute
> force password guessing for Counterpane's
> Password Safe program? Alternatively, does
> anyone have the details of the file format and
> algorithms so I can write one? Bruce's website
> says that it uses Blowfish and that a 2.0 version
> would be published with source, but I don't think
> the 2.0 version was ever published. Does anyone
> have source to it?
>
> Please reply to the list, since I believe the answer
> will be generally useful.
>
> Joe
>
>
>
------------------------------
From: Joseph Reuter <[EMAIL PROTECTED]>
Subject: Re: software protection schemes
Date: Thu, 08 Jun 2000 08:58:45 -0700
Vernon Schryver wrote:
[snip]
> As I thought we agreed the last time someone asked that question
> and was pointed at that trade rag, DO NOT look at "Embedded
> Systems Programming" unless you what you need is at best
> superficial. That magazine is suitable only if you've never
> before thought about the subject or cannot think very well.
>
[snip]
I subscribe to that magazine (why not, it's free) and find it
occasionally useful (sometimes I'm writing embedded software, mostly
I'm writing device drivers). Most of the articles are rather
superficial, but some are actually useful. The regular columnists
are usually useful. Unfortunately, one of them just retired, so I'm
waiting to see if it's worth continuing.
Most of the stuff is stuff I already know, and perhaps know better
than the author. After 33 years in the computer business, I expect
to already know a few things. But, sometimes I'm surprised and
actually learn something, and sometimes I'm entertained, if not
informed. In the long run, I find it worthwhile to spend an
occasional lunch hour reading it.
Later.
Joe
--
Joseph A. Reuter, Wizard-in-Training [EMAIL PROTECTED]
"Olorin I was in my youth in the West that is forgotten."--Tolkien
You can't win, you can't break even, and it's the only game in town.
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Arithmetic Coding
Date: 8 Jun 2000 16:36:38 GMT
[EMAIL PROTECTED] (steffen markert) wrote in
<8hnjhv$oq6$[EMAIL PROTECTED]>:
>Does anybody know about an implementation in C
>or a book or a paper with informations about adaptiv
>arithmetic coding?
>
>Thanx
>
>[EMAIL PROTECTED]
>
>
>
This isn't the best group for info on adaptive compression
but my site has some of the best adaptive compression routines
with the C source code. Mine are tuned for use with enryption
since they don't add information to the compressed product that
allows ones encrypted messages to be weakened. There is a pointer
to matt's site that has the best info on useful with source code
adaptive unadulterated arithmetic coding. But it is in C++
http://members.xoom.com/ecil/compress.htm
------------------------------
From: Andru Luvisi <[EMAIL PROTECTED]>
Subject: Re: questions on TEA
Date: 08 Jun 2000 09:25:44 -0700
Simon Johnson <[EMAIL PROTECTED]> writes:
[snip]
> I believe it was a weekness in the key-shedule... Exactly what changes
> where made in XTEA, i don't know.
>
> However, XDES was a version of Whitened version of des. For this reason
> i have a feeling XTEA is a Whitened version of TEA.
[snip]
It was a related key attack, described in
http://www.counterpane.com/related-key_cryptanalysis.html .
XTEA has a different key schedule. The TEA and XTEA home page is
http://vader.brad.ac.uk/tea/tea.shtml .
Andru
--
==========================================================================
| Andru Luvisi | http://libweb.sonoma.edu/ |
| Programmer/Analyst | Library Resources Online |
| Ruben Salazar Library |-----------------------------------------|
| Sonoma State University | http://www.belleprovence.com/ |
| [EMAIL PROTECTED] | Textile imports from Provence, France |
==========================================================================
------------------------------
From: "IanM" <[EMAIL PROTECTED]>
Subject: Digital Certificates
Date: Thu, 8 Jun 2000 17:38:28 +0100
This may be a stupid question but how does a pc set up with 512 bit RSA use
a certificate with a 1024 bit public key?
Thanks Ian Marriott
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: DES question
Date: 8 Jun 2000 16:38:38 GMT
[We're discussing DES with a changed key schedule and a 64-bit key.]
tomstd <[EMAIL PROTECTED]> wrote:
> This is a bunch of BS and you should know better.
You're spouting rubbish, Tom, and being offensive into the bargain.
> For starters linear cryptanalysis can break DES faster then
> differential cryptanalysis, so even if your line of thinking *were*
> right (which it isn't) you are still wrong.
Err... no, surely that actually strengthens his argument. Linear
cryptanalysis requires only known plaintexts, and fewer of them than
required for differential cryptanalysis.
Let's assume that the key schedule for this variant is `ideal', and it
produces keys which are effectively random and independent.
I don't know how well linear cryptanalysis works when you use
independent round keys. My intuition is that it only increases the
amount of work by about 2^6, and requires a similar increase in the
number of texts required to put the probability of key-bit recovery back
to a sensible level. Thus, you end up with about 2^{49} work for this
phase. You end up with a bunch of equations which relate the bits of
keys in various rounds, constraining the key to be in a fairly small
subset of the available space. Then searching over this space, which
will, I think, be aout 2^{48}, should reveal the final key.
> The problem with saying 'DES can only provide O(2^56) resistance' is
> that you are assuming that differential cryptanalysis can always be
> performed, when in reality it normally can't. Which means the attack
> won't work.
>
> So in reality if you choose independant round keys, you can have
> upto 768-bit single-DES keys.
Note that meet-in-the-middle works efficiently for a key longer than 384
bits. While the storage requirements make the attack impractical now,
you must be assuming that your adversary will be doing impractical
things if you're thinking about using keys this long.
> If you wan't to argue this point (which I suggest you don't) why don't
> you consider the brute force search of the RC5 challenge which has a
> 64 bit key. RC5 with 12 rounds can be broken with O (2^53) effort yet
> *brute force* is what is being used. This is because only a handfull
> of ciphertexts are available.
ITYM `handful'.
The RC5 contest is artificial in nature, and, like the other RSA
contests, is intended to measure how good the world is at performing
various generally-applicable cryptanalytic tasks (such as exhaustive
search of keyspaces, and factoring) rather than attacking specific
ciphers, which is less interesting from their point of view. (If memory
serves, the smaller key-size contents are intended to have propaganda
value in the argument for increasing the key size limits allowed for
export.)
However, what the previous poster suggested was using DES with 64-bit
keys as a general `secure' cipher, in an unconstrained environment. In
such a case, chosen plaintext attacks, such as differential
cryptanalysis, are surely valid when analysing the security of the
construction. Since the work factor for key recovery is quite a bit
smaller than that needed for exhaustive search of the keyspace, it is a
valid conclusion that DES with 64-bit round keys isn't much of an
improvement over standard DES.
> So your point is not valid, and please don't spread such lies.
Please think before posting next time.
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (Charles)
Subject: Random IV Generation
Date: Thu, 08 Jun 2000 16:26:41 GMT
I'm currently puzzling over how to generate an IV to get a Blowfish in
CBC started. I need 64 random bits, but I'm unsure how to actually
collate them. The following options immediately come to mind:
o Use a PRNG to generate 8 random byte values (0-255)
o Hash (i.e. SHA-1) a pool of random data (e.g. system values, mouse
movement, time between character input)
I don't like the idea of using the PRNG, it alleges it has a period of
2^144 but still, not a favourable idea. I haven't seen any worthwhile
PRNG implementations in Visual Basic anyway.
But I'd prefer to use the SHA-1 idea. However, I get 160-bit output
with such a hash. And here's my main question:
how can I fold 160 bits into 64 bits? If I fold them, will they still
be random?
should i just truncate the output to 64 bits, and if i do this will
the output still be random?
is there another viable method? two CRC32 values? (not very secure,
but an idea).
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: DES question
Date: 8 Jun 2000 16:49:14 GMT
Paul Koning <[EMAIL PROTECTED]> wrote:
> If you're not going to use DES as is -- which is wise -- then just
> substitute another well-analyzed cipher with a decent key size. 64
> isn't enough to be worth it even considering the other issues. 3DES
> will do nicely; for high speed software crypto, Blowfish or IDEA (give
> or take some patent licensing issues) are reasonable choices. Or
> CAST, I suppose. That one tends not to get mentioned when the other
> two are, I'm not sure why not. Less marketing?
IDEA's claim to fame is that Phil Zimmerman used it in PGP. It was just
about the only choice other than DES, so you can't really blame him for
that. Apart from this, IDEA is just another patented block cipher
which, while academically interesting, probably wouldn't have been used.
Blowfish is free, simple, fast and strong. Bruce Schneier is also an
excellent publicist. I can see why it does well.
CAST-128 is slower than Blowfish. I think that's down to the
key-dependent rotations: apart from that there's very little difference
between the two in terms of round structure. It seems to be quietly
included in all sorts of places -- PGP 6, for example. If you read the
CAST-256 AES submission, you'll have noticed that the Canadian
Government have said that CAST-128 can be used for all `Designated
information', whatever that means. Both fully-specced CAST ciphers are
now defined by RFCs too, and I think included in IPsec. Both are
licensed free-of-charge worldwide for any use, but the design procedure
is patented. Maybe the patent is enough to dampen enthusiasm for CAST
ciphers (I doubt this), or maybe they're just not very interesting.
-- [mdw]
------------------------------
From: "Joseph Smith" <[EMAIL PROTECTED]>
Subject: Re: Brute forcing for Counterpane's Password Safe
Date: Thu, 08 Jun 2000 16:51:47 GMT
I appreciate all the discussion about password
choices. Actually I was planning on using a dictionary
attack, not try-all-characters, particularly since I have
a large list of significant names, places, dates, etc.
The legal discussion about rights has been interesting
and it makes sense to me that people should be
skeptical about my motives. Indeed Joe Smith is
a pseudonym, though it is slightly less obvious than
John Doe. I use it to avoid spam and to indicate that
I am acting as an individual, not a representative of
some company.
The conclusion from this newsgroup and from some
web searching I have done is that there does not exist
a public program for testing passwords used to protect
the data files for Counterpane's Password Safe.
So far what I have found about the file format is that the
first 28 bytes remains fixed when the file is saved, and
the remaining bytes change whenever any entry changes.
The first 28 bytes change when the password is changed.
My guess is that this part holds a salt and password
hash, since the program only complains about incorrect
passwords if these bytes are changed. Surprisingly,
changing the other bytes does not produce an error about
tampering with the file.
By changing bytes with a hex editor it I have determined
the order in which fields are stored and that CBC mode is
used (no surprise) and that the variable data (29th byte
onward) starts with an 8-byte IV (again no surprise).
The data fields seem to be stored as a 32 bit length followed
by data blocks, so some changes cause the program
to get out-of-memory errors because they produce excessive
field lengths.
Again thanks for you comments.
Joe
------------------------------
From: Mike Rosing <[EMAIL PROTECTED]>
Subject: Re: software protection schemes
Date: Thu, 08 Jun 2000 11:57:42 -0500
Vernon Schryver wrote:
> As I thought we agreed the last time someone asked that question and was
> pointed at that trade rag, DO NOT look at "Embedded Systems Programming"
> unless you what you need is at best superficial. That magazine is suitable
> only if you've never before thought about the subject or cannot think very
> well.
I don't disagree. It's just that the original question didn't even
understand
the problem, and that article would give them a place to start.
Just because something is worthless to you doesn't make it worthless in
general.
Patience, persistence, truth,
Dr. mike
------------------------------
** 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
******************************
