Cryptography-Digest Digest #286, Volume #14 Thu, 3 May 01 09:13:01 EDT
Contents:
Re: DES sample vector ([EMAIL PROTECTED])
Re: Random and not random (Mok-Kong Shen)
Re: LFSR Security (Tim Tyler)
Re: DES sample vector (Mark Wooding)
Re: __(Q) The state of Hyperelliptic cryptography, submitted to sci.crypt. (Robert
Harley)
Re: information theoretic stream cipher ("Tom St Denis")
Re: A Question Regarding Backdoors ("Tom St Denis")
Re: research on polymorphic crypto/Best Possible Privacy? (Mark Wooding)
Re: cryptographicaly secure prng ("Tom St Denis")
Re: DES sample vector (Luis Duarte)
Re: ancient secret writing ("Mark Lomas")
Re: research on polymorphic crypto/Best Possible Privacy? (Mark Wooding)
Knapsack Chaff (Gary)
Re: DSA in GF(2^W)? (Roger Fleming)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Subject: Re: DES sample vector
Date: Thu, 3 May 2001 08:06:25 GMT
=====BEGIN PGP SIGNED MESSAGE=====
Hash: RIPEMD160
Roger Schlafly wrote:
> > I'd like to implemente DES algorithm in java but i don't manage to find
> > test vector ! :-(
>
> Try this. The key "\x0E\x32\x92\x32\xEA\x6D\x0D\x73" will encrypt
> all zeros to all 0x87.
I wonder how this is found
probably by checking all the keyspace...
== <EOF> ==
Disastry http://i.am/disastry/
http://disastry.dhs.org/pgp <----PGP plugins for Netscape and MDaemon
^--GPG for Win32 (supports loadable modules and IDEA)
^---PGP 2.6.3ia-multi03 (supports IDEA, CAST5, BLOWFISH, TWOFISH,
AES, 3DES ciphers and MD5, SHA1, RIPEMD160 hashes)
=====BEGIN PGP SIGNATURE=====
Version: Netscape PGP half-Plugin 0.15 by Disastry / PGPsdk v1.7.1
iQA/AwUBOvD1WjBaTVEuJQxkEQPIrgCdG9dxRXQIQCvy6b7aWOU7OYxGPJoAn0LR
sL83gqpyhmvUdcoojnEAqjug
=UywN
=====END PGP SIGNATURE=====
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Random and not random
Date: Thu, 03 May 2001 11:18:57 +0200
Matthew Skala wrote:
>
> Tim Tyler <[EMAIL PROTECTED]> wrote:
> >: I suspect that you know this and are pulling our legs [...]
> >
> >John's article seems quite serious and perfectly correct to me.
> >
> >I too can easily imagine advocating applying a conventional cypher -
> >in addition to an OTP - in order to improve the security of the latter.
>
> As a backup in case the OTP is compromised (by operator error or
> key-distribution failure) it may make sense. John proposed it for a much
> different purpose: as a measure to alleviate uninformed people's concerns
> that "the OTP might randomly have a pad of all zeroes, resulting in no
> encryption!". It might serve the goal of alleviating the uninformed
> people's concerns, but it does so only by illusion. Instead of an OTP by
> itself having a pad of all zeroes and a ciphertext equal to the plaintext,
> it's equally likely that the OTP plus conventional cipher would undo each
> other and also result in no encryption.
>
> Any chain of encryptions with the perfect secrecy property of an OTP will
> have that possibile "failure mode" - it's an inescapable part of perfect
> secrecy, because if there is no possibility of your transmitting the
> plaintext unencrypted, then every transmission reveals the tiny clue that
> whatever your plaintext is, it *isn't* what you transmitted.
I don't exclude that I may have committed some subtle
logical blunders in the following argumentation. However,
I haven't yet been able to detect any myself. Hence I am
posting it for discussion.
One has to note the fact that an ideal OTP is a source
that is infinite in capacity. When one arbitrarily
discards some finite segments of it, it remains an
infinite source. So suppose one employs a statistical
test to discard some segments of the sequence output from
the source. We can first consider that these segments are
employed to encrypt some dummy (unimportant) messages and
one actually sends them together with the proper messages
that are encrypted with the remaining segments of OTP that
pass the chosen test. Now from theory, all messages are
secure, i.e. the opponent can't gain any knowledge from
any part of the total stream of the ciphertexts, whether
these correspond to dummy messages or proper messages.
This means we could omit sending the dummy messages. The
netto result is therefore that we can use a statistical
test to discard (waste) part of what is generated by the
OTP source and yet retain the theoretical property of
perfect security of OTP.
Thanks for your comments in advance.
M. K. Shen
------------------------------
Crossposted-To: sci.crypt.random-numbers
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: LFSR Security
Reply-To: [EMAIL PROTECTED]
Date: Thu, 3 May 2001 09:23:05 GMT
In sci.crypt David Wagner <[EMAIL PROTECTED]> wrote:
: Tim Tyler wrote:
:>It's easy to quantify how much as well - for a shift register of length
:>n, you get n unknowns from the unknown initial state of the register, and
:>n unknowns from the unknown taps - one for each possible position.
:>
:>To recover all the details of the system, you thus need 2*n linear
:>equations - and consequently 2*n bits of output - just the same as
:>the BM algorithm needs, in fact.
: But you don't get 2n linear equations. If you work out what the
: equations are, they are nonlinear. Try it on an example and see
: for yourself!
Hmm, yes - multiplications with the XORs. Thanks for pointing out my error.
It appears my next best approach is likely to involve about
2*n bits of output - but also a brute force search through the
space of those elements of the state not revealed in some string
of n consecutive outputs :-(
--
__________
|im |yler Try my latest game - it rockz - http://rockz.co.uk/
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: DES sample vector
Date: 3 May 2001 09:47:10 GMT
Roger Schlafly <[EMAIL PROTECTED]> wrote:
> Try this. The key "\x0E\x32\x92\x32\xEA\x6D\x0D\x73" will encrypt
> all zeros to all 0x87.
No it won't. It'll encrypt all zeros to cddb30ef2fef1aff. It will also
encrypt 8787878787878787 to 0000000000000000, but that's not what you
said. ;-)
-- [mdw]
------------------------------
From: Robert Harley <[EMAIL PROTECTED]>
Subject: Re: __(Q) The state of Hyperelliptic cryptography, submitted to sci.crypt.
Date: 03 May 2001 12:27:48 +0200
kctang <[EMAIL PROTECTED]> writes:
> Does Hyperelliptic curves cryptography possess advantages or
> *potential* advantages over elliptic curves cryptography?
Probably doesn't possess any major advantages. There could be some
minor ones e.g., getting larger groups over smaller base fields.
> What are the *existing* view points on its following aspects
> such as
> Key-length, Efficiency and Performance,
Key-length should presumably be similar to elliptic. Performance
appears to be a little worse e.g., 30 or so multiplications and 2
inversions for an operation in the jacobian of a genus 2 curve, versus
say 3 mults and 1 inv for elliptic albeit in a field twice the size.
> Discrete Log problem,
Only hyperelliptic curves of genus 2 or 3 should be used, since
otherwise index calculus is faster than generic attacks.
> Generating secure curves, point counting .... etc. ?
Finding secure random curves by point-counting was impossible until
very recently. But now it is possible e.g., I recently counted a
genus 2 jacobian over GF(2^4000). I could tell you how but I would
have to kill you. :)
> Thanks, kctang
Welcome.
> PS.
> Please use simple sentences so that I can understand.
Ooops. Well you are asking about a complex area...
Rob.
.-. [EMAIL PROTECTED] .-.
/ \ .-. .-. / \
/ \ / \ .-. _ .-. / \ / \
/ \ / \ / \ / \ / \ / \ / \
/ \ / \ / `-' `-' \ / \ / \
\ / `-' `-' \ /
`-' http://www.xent.com/~harley/Top.html `-'
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: information theoretic stream cipher
Date: Thu, 03 May 2001 10:51:37 GMT
"Henrick Hellström" <[EMAIL PROTECTED]> wrote in message
news:9cr0hp$1v$[EMAIL PROTECTED]...
> "Tom St Denis" <[EMAIL PROTECTED]> skrev i meddelandet
> news:AO2I6.4730$[EMAIL PROTECTED]...
> >
> > "Henrick Hellström" <[EMAIL PROTECTED]> wrote in message
> > news:9cq94h$cl1$[EMAIL PROTECTED]...
> > > If A is truly random, you could dispose of B and exchange step #1 for
> C_i
> > =
> > > M_i xor A, and you would have an OTP.
> >
> > I mean that it's not truly random but uniformly distributed (or nicely).
> > The idea is to analyze the proposal disjunct of the update function.
> While
> > that won't give the complete picture it does allow us to analyze the
first
> > step wrt any form of analysis irrespective of the update functions.
>
> Yes, it does allow you. The update function does not increase the security
> level with a factor much larger than it's security of it's own. If there
is
> an attack against both of the update functions, it will not be prevented
by
> your combiner, but only made a little bit harder. I have already
> demonstrated that any adaptive attack against either A or B will still
work
> with twice the amount of queries. If there are statistical attacks against
> both A and B, both will still work with more known plain text. For
example,
> if both A and B are biased in such way that there are some values d_a, d_b
> such that the probabilities P(d_a = A_i+1 - A_i) = p_a and P(d_b = B_i+1 -
> B_i) = p_b, then the attacker would have a probability equal to p_a*p_b to
> find an occurance of both differences at the same time.
Yes true, but even if the update were a simple LCG then all values of in Z*p
would be equal probable.
> > > Note that you would only have to make two queries to the cipher at
> > position
> > > i to determine the value of A at that position, namely M_i = x, M'_i =
> > x+1.
> > > Clearly, A = C'_i - C_i = (x+1)*A + B - x*A - B modulo p. Three
queries
> > > would be sufficient for a high probability distinguisher for
> > non-randomness,
> > > because you could query M_i = x, M'_i = x+1, M''_i = x+2, and if
C'_i -
> > C_i
> > > = C''_i - C'_i modulo p the distinguisher would output that your
> combiner
> > > was used.
> > >
> > > If you don't allow such adaptive attacks, then you might as well use
> xor.
> >
> > It's a stream cipher not a a block cipher so the condition M_i and M'_i
is
> > impossible...
>
> I hope you are able to justify that. What if it is a seekable stream
cipher?
> Then an attacker with access to an encryption device would only have to
> reset the position once to do what I described.
That's not a rational argument. Suppose you used the same key in RC4 twice
under a chosen plaintext attack. The first time you encrypt the real
message the second time you encrypt an attackers message, etc. Or if I
remove 16 xor's in DES I can break it very easily, etc...
You wouldn't normally re encrypt at the same spot.
> > Also you only need two queries if it were possible.
>
> No, not if A really is secure. C'_i - C_i = A would then be a pseudorandom
> number. The attacker would not know if he had got an answer from your
oracle
> or a true random function any more than he would know that if he was
handed
> A directly.
Given F(x) = ax + b, F(x) - F(x - c) = ac, thus you know 'c' so you know
'a'. This only requires two texts. Once you know 'a' you find 'b' easily.
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: A Question Regarding Backdoors
Date: Thu, 03 May 2001 10:53:10 GMT
"Tim Smith" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> On Mon, 30 Apr 2001 11:11:33 GMT, Tom St Denis <[EMAIL PROTECTED]>
wrote:
> >Then he should ask the right question which is "Is it legal to use
256-bit
> >symmetric keys in the US". This has nothing todo with AES or possible
>
> That's not the right question. The right question is whether he has to
> put a backdoor into his system, which is what he asked. No one else
> seems to be having trouble understanding the question, so the problem
> is you, not him.
To me that's the last thing a serious cryptographer should be asking. Most
have problems enough with inadvertant bugs that cripple systems (PGP,
Netscape, etc...) let alone intentional bugs or faults.
Tom
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: research on polymorphic crypto/Best Possible Privacy?
Date: 3 May 2001 11:02:15 GMT
Shea J. Hawes <[EMAIL PROTECTED]> wrote:
> I'm looking for research that anyone may have done regarding the product
> Best Possible Privacy. The underlying technology is described as a
> polymorphic encryption scheme. There is a description of the algorithm
> at www.identification.de/crypto/descript.html with a related site
> selling the product at www.ciphers.de/bpp. I have searched for other
> references to either of these pages and found nothing so far. I have
> read the snake oil faq and this seems to fall into that category but I
> am not an expert so I turn to those of you who are.
I agree. It smells like snake-oil.
The idea it seems to be based on -- twiddling `the algorithm' in a
key-related way -- is hardly new, and I don't think I've seen any
variant which actually turned out to have any merit. There are usually
major problems with weak keys, for example.
I'd recommend avoiding this system, and any others that look like it.
Stick with fully-published ciphers.
-- [mdw]
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: cryptographicaly secure prng
Date: Thu, 03 May 2001 11:13:53 GMT
"Charles Blair" <[EMAIL PROTECTED]> wrote in message
news:uo3I6.2310$[EMAIL PROTECTED]...
> Is something wrong with the Impagliazzo-Naor prng? It seems
> very attractive in not needing any multiplications.
RC4 doesn't need multiplications either.
What is the Impagliazzo-Naor PRNG anyways?
Tom
------------------------------
From: [EMAIL PROTECTED] (Luis Duarte)
Subject: Re: DES sample vector
Date: Thu, 03 May 2001 10:16:51 GMT
On Thu, 03 May 2001 07:31:11 GMT, =?iso-8859-1?Q?Fr=E9d=E9ric?= Donnat
<[EMAIL PROTECTED]> wrote:
>But i didn't manage to find an example describing the result for each round. :-(
>So, if someone can point me to a site where i can find an implementation having a dbug
>mode to see these result, i would be very greatfull. ;-)
>
>Bests regards.
>Fred
>
I don't remember where I got these sample vectors but I find them
pretty useful.
19 KEY DATA PAIRS WICH EXERCISE EVERY S-BOX ENTRY
KEY PLAIN CIPHER
7CA110454A1A6E57 01A1D6D039776742 690F5B0D9A26939B
0131D9619DC1376E 5CD54CA83DEF57DA 7A389D10354BD271
07A1133E4A0B2686 0248D43806F67172 868EBB51CAB4599A
3849674C2602319E 51454B582DDF440A 7178876E01F19B2A
04B915BA43FEB5B6 42FD443059577FA2 AF37FB421F8C4095
0113B970FD34F2CE 059B5E0851CF143A 86A560F10EC6D85B
0170F175468FB5E6 0756D8E0774761D2 0CD3DA020021DC09
43297FAD38E373FE 762514B829BF486A EA676B2CB7DB2B7A
07A7137045DA2A16 3BDD119049372802 DFD64A815CAF1A0F
04689104C2FD3B2F 26955F6835AF609A 5C513C9C4886C088
37D06BB516CB7546 164D5E404F275232 0A2AEEAE3FF4AB77
1F08260D1AC2465E 6B056E18759F5CCA EF1BF03E5DFA575A
584023641ABA6176 004BD6EF09176062 88BF0DB6D70DEE56
025816164629B007 480D39006EE762F2 A1F9915541020B56
49793EBC79B3258F 437540C8698F3CFA 6FBF1CAFCFFD0556
4FB05E1515AB73A7 072D43A077075292 2F22E49BAB7CA1AC
49E95D6D4CA229BF 02FE55778117F12A 5A6B612CC26CCE4A
018310DC409B26D6 1D9D5C5018F728C2 5F4C038ED12B2E41
1C587F1C13924FEF 305532286D6F295A 63FAC0D034D9F793
------------------------------
From: "Mark Lomas" <[EMAIL PROTECTED]>
Subject: Re: ancient secret writing
Date: Thu, 3 May 2001 12:10:45 +0100
I am reminded of a wonderful book, "N'Heures Souris Rames", by Ormonde
de Kay which purported to contain medieval French poetry. If you read the
title aloud you will discover what it really contains.
Mark
"Mok-Kong Shen" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
>
> "Douglas A. Gwyn" wrote:
> >
> > Mok-Kong Shen wrote:
> > > I tend also to think that there is a substantial probability
> > > of the more recent stuffs like the Voynich Manuscript
> > > being a hoax intended to fool people.
> >
> > The Voynich manuscript is hardly "recent".
> > Also, if it is a hoax, it is an incredibly subtle one;
> > for example, there are four (if I recall correctly) distinct
> > "hands" (textual styles), which is a totally unnecessary detail
> > for a hoax.
> >
> > > More sensible seems to spend resources on the very ancient
> > > findings of archeology. But these are apparently very very
> > > hard to attack, since we have no knowledge at all of the
> > > languages involved.
> >
> > Which languages did you have in mind? Several have in fact
> > been deciphered.
>
> I meant stuffs like the Diskos of Phaistos (see Bauer's
> book). There are, if I don't err, also quite a number of
> written remnants of comparatively recently died-out cultures
> of small isolated tribes, the 'decryption' of which could
> certianly be of some scientific value.
>
> BTW, I like to take this opportunity to mention a matter
> which has only a very remote association with the topic
> of the current thread. In some living languages there are
> dialects that are so different from one another that,
> when these are transcribed purely phonetically with the
> Latin alphabet, they could lead to entirely different
> looking character sequences. (Example: a number of dialects
> in southern China.) This could lead to some confusion of
> the opponent, if he doesn't have enough resources/competency
> to tackle that. Here is a personal story concerning a
> European language: Once I got a piece of writing which
> belongs to the so-called Wiener Dichtung, a kind of phonetic
> transcription of a lyric poetry when being pronounced in the dialect of
> German in Vienna. I showed it to an Austrian-born
> colleage and asked her whether she happended to know the
> language in which it was written. She plainly failed the
> task, until I asked her to attempt to read that piece of
> writing aloud.
>
> M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: research on polymorphic crypto/Best Possible Privacy?
Date: 3 May 2001 12:16:57 GMT
Mark Wooding <[EMAIL PROTECTED]> wrote:
> I agree. It smells like snake-oil.
Having wandered around their web-pages a bit more, my opinion is as it
was before. It's definitely snake-oil. Doesn't seem to have been
mentioned yet in Schneier's Crypto-Gram, which is a shame.
One interesting pointer is that, almost throughout, the keys are
referred to as `passwords'. It seems symptomatic of a mind that hasn't
moved beyond mangling files to protect them from a kid sister.
There are some other gems. I particularly liked `No plug-ins => No
security holes'.
Enough of this. I'm getting too depressed.
-- [mdw]
------------------------------
From: Gary <[EMAIL PROTECTED]>
Subject: Knapsack Chaff
Date: Thu, 3 May 2001 08:36:26 -0400
Knapsack Chaff
N completely randomly generated numbers are added to a conventionally
generated knapsack set.
The originator ends up with 2^n possible solutions for any decryption, for
small n at about 20-24 this doesn't pose such a big problem when some kind
of
authentication, such as the knowing hash of the unencrypted solution.
Doesn't this however cause a problem with regard to an eavesdropper cracking
the lattice?
G.
------------------------------
From: [EMAIL PROTECTED] (Roger Fleming)
Subject: Re: DSA in GF(2^W)?
Date: Thu, 03 May 2001 11:05:15 GMT
In article <bP6H6.2$[EMAIL PROTECTED]>, "Roger Schlafly"
<[EMAIL PROTECTED]> wrote:
[...]
>I'm not sure I follow. What public-key algorithm uses theory that is
>over 2000 years old? Arithmetic is that old, but that's about all.
You commit the common sin of unfairly deprecating the intelligence of our
forebears. The ancient Greeks in fact made substantial inroads into number
theory long before the birth of Christ.
Ever heard of Erastothenes' Sieve, the great grand-daddy of all prime search
algorithms? Erastothenes died in 194 BC. (He is also the guy who calculated
the circumference of the earth with an error of only 1.4%).
Then there's Euclid: Books VII to IX of Euclid deal almost exclusively with
number theory; they include, inter alia, the Euclidean algorithm (duh!), and
the relation between Mersenne primes and perfect numbers. The exact date of
writing these books is not known but about 275 BC is generally accepted; they
are, however, generally regarded by historians as a compilation,
systematisation,and refinement of even older mathematical knowledge.
While we're at it I'll also mention Diophantus, who was probably a first or
second century AD man, but noted for making major contributions to number
theory (and also algebra, which also is much more than 2000 years old).
(Aside: it was in the margin of a Latin translation of Diophantus'
"Arithmetica" that Fermat wrote his famous "theorem").
In short, the assertion that the mathematicians of 2000 years ago knew no
number theory is completely wrong, and the assertion that they knew little
more than arithmetic is offensively wrong.
------------------------------
** 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
******************************
