Cryptography-Digest Digest #107, Volume #12 Mon, 26 Jun 00 04:13:01 EDT
Contents:
Re: newbieish question (tomstd)
where start for engine computer encyrption system ([EMAIL PROTECTED])
Early Draft of the TC5 paper available (tomstd)
Re: Quantum computing (Bill Unruh)
Re: Public key algorithm conversion - does it possible? (acoola)
Re: libdes: des_SPtrans ([EMAIL PROTECTED])
Re: DES 64 bit OFB test vectors (Hideo Shimizu)
Re: "And the survey says" ("Scott Fluhrer")
Re: DES and questions ("Scott Fluhrer")
Re: Variability of chaining modes of block ciphers (Mok-Kong Shen)
Re: Variability of chaining modes of block ciphers (Mok-Kong Shen)
Re: How Uncertain? (Mok-Kong Shen)
Re: Announce: Catacomb 2.0.0pre2 now available (Mark Wooding)
----------------------------------------------------------------------------
Subject: Re: newbieish question
From: tomstd <[EMAIL PROTECTED]>
Date: Sun, 25 Jun 2000 20:35:49 -0700
Benjamin Goldberg <[EMAIL PROTECTED]> wrote:
>In a recent post I put up, I said that a function I was looking
for
>should have the following two properties:
>
>1) For any fixed key, if any bit changes in the input,
approximately
>half of the bits in the output should change, and
More specifically half the *round key* bits should change not
the plaintext/ciphertext bits. See below.
>2) For any fixed input, if any bit changes in the key,
approximately
>half of the bits in the output should change.
>
>I was wondering... are these properties always considered
important in
>cryptographic functions?
No they are not. They are mainly a consequence of secure block
ciphers. For example if there is a linear correlation between
input bits and key bits then obviously flipping a bit will not
change half the bits with an even probability (hence it's
linear!!!).
In your comment about the master key, it's half the round key
bits should change which in turn would cause the half of the
ciphertext bits to change...
Tom
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
From: [EMAIL PROTECTED]
Subject: where start for engine computer encyrption system
Date: Mon, 26 Jun 2000 04:20:01 GMT
I want to take in data off of my car's engine computer, encrypt it,
store it and only allow me and a "GM" mechanic to get the information
off. I think they should all be able to get the information without
each others permissions. Where should I start looking to design such a
system? What sort of pieces do I need? What can I buy that would fit
into this puzzle?
I think I would need some sort of device to get the data from the
engine computer (I have that) and then another device to encrypt it. I
would have to already have PKI system in place? Please let me know
what/where I should be looking.
This is a home project I am undertaking. Fun huh?! Hope I get through
the first week. I wanted the best info to start, so I came here.
Many thanks.
--Matt
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
Subject: Early Draft of the TC5 paper available
From: tomstd <[EMAIL PROTECTED]>
Date: Sun, 25 Jun 2000 21:59:15 -0700
My few hours of work are available on my website (see below). I
have started some basic cryptanalysis but by no means complete.
I would like some help working on this cipher, so anyone with a
few hours to spare please let me know.
Thanks,
Tom
--
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: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: Quantum computing
Date: 26 Jun 2000 05:37:36 GMT
In <[EMAIL PROTECTED]> "Douglas A. Gwyn" <[EMAIL PROTECTED]> writes:
>Bill Unruh wrote:
>> Uh, no. Error correction itself requires incredibly unnoisy qbits. The
>> raw level of error must be less than about 10^-4 for one even to dream
>> of error correction.
>Wrong again.
Interesting argument. I work in quantum computing. What is the basis for
your statement?
------------------------------
From: acoola <[EMAIL PROTECTED]>
Subject: Re: Public key algorithm conversion - does it possible?
Date: Mon, 26 Jun 2000 05:27:07 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Mark Wooding) wrote:
> It's trivial to derive an ElGamal public key from the private key. If
> the prime modulus is p, the generator is g, and the private key is x
you
> compute the public key as g^x mod p.
Maybe it's my fallacy but it seems to me that it's no trivial for
cryptanalyst to get g.
ElGamal Encryption
Public Key:
p prime (can be shared among a group of users)
g < p (can be shared among a group of users)
y = g^x mod p
Private Key:
x < p
Encrypting:
k choose at random, relatively prime to p - 1.
a (ciphertext) = g^k mod p
b (ciphertext) = y^kM mod p
Decrypting:
M (plaintext) = b/a^x mod p
Cryptanalyst know only a, b, M, x and p.
> What's the difference between what you want to do and a digital
> signature?
I'd like to unite properties of digital signature and enciphering and
I want to find out does it possible to make it at a time.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: libdes: des_SPtrans
Date: Mon, 26 Jun 2000 06:09:20 GMT
yes, you're right. i did 8*64*8 instead of 8*64*4. in this case my gain
will be a lot less when i consider the code size required to generate
the table at runtime. i guess i'll still give it a try. thanks.
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Svend Olaf Mikkelsen) wrote:
> [EMAIL PROTECTED] wrote:
>
> >hi all,
> >
> >i'm porting a portion of libdes to a handheld terminal with very
little
> >code memory (32K). if i can get to calculate des_SPtrans table
> >in "spr.h" i can save 4K, that makes 12.5%. does anyone know the
> >algorithm to calculate the table? i ananlysed it for some time but
> >could not get to an answer. thanks in advance.
>
> Note that des_SPtrans is 2048 bytes, nok 4K.
> --
> Svend Olaf
>
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Hideo Shimizu <[EMAIL PROTECTED]>
Subject: Re: DES 64 bit OFB test vectors
Date: Mon, 26 Jun 2000 15:12:05 +0900
See http://www.yokohama.tao.go.jp/shimizu/des_test.html .
Jack Spencer 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.
>
> Thanks,
>
> JS
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: "And the survey says"
Date: Sun, 25 Jun 2000 23:31:03 -0700
Jonathan Edwards <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
>
> On Sun, 25 Jun 2000, Scott Fluhrer wrote:
>
> >
> > For that matter, I don't know of any cipher (practical or impractical)
> that
> > has property #1 (with an Oracle, you can break an OTP trivially).
> >
> > [1] The constraint on the Oracle is that you can't ask the decryption of
the
> > input ciphertext.
>
> OK, I'm dense.
>
> How does the Oracle break the OTP? Do you ask it the bits of the key?
The definition of constrained Oracle I'm using: a magic box (that runs in
O(1) time, in case it matters) that will encrypt an arbitrary message using
the key used to encrypt the test ciphertext, and will decrypt an arbitrary
message using that same key, except for the specific case of the test
ciphertext itself.
Then, it's easy: ask the Oracle to encrypt the ciphertext. Since OTP is
self-inverse, that will give you the plaintext. Alternatively, flip a bit
in the ciphertext, ask it to decrypt that (it's no longer the test
ciphertext, so the constraint isn't in effect), and then flip the bit back.
This is really the observation that OTP isn't secure if you reuse the
keystream (that is, if it isn't a *one* time pad), combined with the
observation that chosen plaintext attacks inherently reuse keystream when
applied to OTP's, at least in the simple-minded way I've abstracted chosen
plaintext attacks.
--
poncho
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: DES and questions
Date: Sun, 25 Jun 2000 23:39:39 -0700
rick2 <[EMAIL PROTECTED]> wrote in message news:rb-29667B.16575825062000@news...
> I have two more questions about implementing DES in a program. (Feel
> free to Dope-Slap(TM) me if these are too close to outright idiotic.)
>
> 1. It turns out that 3-DES is kind of slow, so any speed-up tricks
> would be worth it. So, not very brilliant, but what about 2-DES?
> Would that have a encryption strength of 128 (or should it be 112)
> bits? Geez, that seems pretty strong, no? Especially if people have
> been using only two different keys for 3 rounds of DES, why not just
> do the two with two keys?
It turns out there's a meet-in-the-middle attack that will, with O(2**M)
memory and a couple known plaintext/ciphertext pairs, break it in
O(2**(112-M)) time, for M<=56. This isn't much better than single DES if
you assume the attacker has lots of memory.
The same attack, applied to 3DES, breaks it in O(2**(168-M)) time, again for
M<=56. Now, this is a reasonable improvement over DES, even if the attacker
has O(2**56) memory.
--
poncho
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Variability of chaining modes of block ciphers
Date: Mon, 26 Jun 2000 10:00:52 +0200
Scott Fluhrer wrote:
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> > Scott Fluhrer wrote:
> > > Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> > > > The most popular block chaining mode seems to be CBC.
> > > > There is also PBC which chains with plaintext blocks.
> > > > One can also accumulate the previous blocks for doing the
> > > > chaining and use plaintext as well as ciphertext for
> > > > chaining. (I used this in one of my own designs.) By
> > > > combinatorics this gives 8 variants. Obviously one can
> > > > also use modular addition instead of xor and do some
> > > > random rotations if one likes. I think that the variability
> > > > of chaining modes could be advantageousy exploited such
> > > > that the actual chanining mode used in a message has to be
> > > > guessed by the opponent, thus redering his task much more
> > > > difficult.
> > > Why would it? All these operations can be summarized as:
> > >
> > > C_i = Encrypt( F( P_i, C_{i-1}, P_{i-1} ) )
> > >
> > > for a relatively small set of F's, where:
> > >
> > > P_i is the ith plaintext block
> > > C_i is the ith ciphertext block
> > > Encrypt is the underlying block cipher (on a single block in encrypt
> mode)
> > >
> > > Given that the number of possible F's is relatively small, and assuming
> that
> > > P_i, P_{i-1} are known (that is, this is the known-plaintext attack),
> the
> > > attacker can easily compute all 8 possible values of F( P_i, C_{i-1},
> > > P_{i-1} ), and then do a brute force calculation of:
> > >
> > > Decrypt( C_i )
> > >
> > > looking for any of the 8 possible values. When he finds one, it is easy
> to
> > > verify if he got the key, or a false hit.
> > >
> > > This allows the attacker to look through all 8 possibilities with a
> > > relatively small additional effort beyond a brute force search of the
> > > underlying block cipher. Thus, you have gained no additional security
> for
> > > your additional complexity.
> >
> > How about the case where IVs are secret? I am not claiming tremendous
> > gain but some gain that may overweigh the cost.
> As I mentioned upthread, it doesn't help if the attacker can select i>1.
Tell me how do you proceed to analyse in the case the chaining mode
uses sums of previous plaintexts and ciphertexts. I was saying there
are at least 8 varaints of chaining modes but not claiming at all that they
are all good. If there are a few such that using each one of them
is equivalent to strengthening the cipher at least by a certain nontrivial
amount and if you manage to also dynamically choose amount these,
then you achieve something additional (above what is offered by
a single one of these). If you always use one of the good chaining modes,
then it is also o.k. in my opinion. Maybe I haven't understood what you
wrote previously.
> > As to added complexity,
> > I'll say that's very trivial according to experience of implementation
> > of one of my own algorithm.
> I take it you didn't try to implement the algorithm in hardware. In any
> case, it appears that to implement this efficiently, you need either to have
> N copies of the encryption/chaining routine (uses more memory), or a single
> copy that can dynamicly select between chaining modes (which is a bit
> slower). Now, since it appears that this doesn't gain any additional
> security, I don't see how either cost is worth it, even though the costs are
> fairly small in both cases.
>
I think that, if you implement a choice of chaning modes, you will never
implement N copies of your cipher, each with a different mode. There
may be a tiny little bit of cost due to the choice. I don't know, since I
have too little hardware knowledge. Afterall, it is a ubiquitous fact that
you have to pay something for anything (useful) in this world. One has
always to make a cost/benefit analysis depending on the situation at
hand. You last sentence has been covered above.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Variability of chaining modes of block ciphers
Date: Mon, 26 Jun 2000 10:00:41 +0200
Scott Fluhrer wrote:
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> > Mark Wooding wrote:
> > > Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> > > > O.k. We could discuss on that. Please give your arguments. (Note that
> > > > this issue is independent of the issue of whether chaining only adds
> > > > a couple of bits to the key space.)
> > >
> > > No. Just using *a* chaining mode doesn't affect the key space at all.
> > > Using an secretly chosen chaining mode will add a few effective key
> > > bits.
> >
> > If you use a secret IV, that should help a little bit.
>
> Depends on the mode. If we're talking to some variant of CBC or CFB, it
> won't help at all (as long as the message is at least two blocks long) --
> the attacker selects some block other than the first.
That is the reason why I personally don't like CBC. (See one of
my follow-ups in response to Tim Tyler.) Such discussions are
among what I intended to elicit with my original post.
> > > > (I could have instead given an example like this: My boss, who happens
> > > > to be a friend of an amateur crypto designer, insists on using and
> > > > buying the software developed by the latter, the security of which I
> > > > am however not very sure. Do you find this version of an example
> > > > better for you?)
> > >
> > > Not really. Either explain to your boss that he needs to get a clue
> > > from somewhere, or find a different boss.
> >
> > I am not sure that's always a recommendalble stragegy (especially
> > in times of unemployment problems).
>
> And even if that's not a concern, it'd be a shame to blow off a good boss
> with one quirk. Alternative strategy: implement the amateur crypto design,
> but preprocess the plaintext just a bit, so of like a "prewhitening" phase.
> For example, pass it through Rijndael first. (1/2 :-)
You are distorting the discussion context. We are discussing the
possibilities to obtain some improvements upon a given cipher
with some chaining modes, not discussing using two or more ciphers.
(I personally favour multiple encryptions, but that's an entirely
different issue.)
> > > > O.k. Suppose that the best cipher you could manage to get is not
> > > > good enough, but almost. Suppose adding the strength due to chaining
> > > > renders it above the capability of the opponent. Would you care to use
> > > > chaining in this situation or not?
> > >
> > > I'm disputing whether this situation can happen at all! It calls for an
> > > impractically fine judgement of the adversary's capabilities.
> >
> > I was providing a 'boundary' case for consideration. One's judgement
> > in crypto is indeed in my opinion necessarily fairly subjective and gross
> > in general. But there could also be (admittedly rare) special situations
> > where one could have sufficient materials to do fairly accurate estimate
> > of the opponent's capability. For example, if one somehow knows
> > the computing power of the opponent and brute force is the analysis
> > method being used.
>
> You rarely get precise estimates of the computer power available to the
> opponent. If nothing else, opponents tend to stay around for a while, and
> the computer power available tends to rise unpredictably over time.
We were discussing whether the situation I mentioned can happen at all,
not how frequent it can exist. There are also possible situations where
one is 'powerless' in security and one could just as well give up
encryption, namely if the opponent is (almost) omnipotent.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: How Uncertain?
Date: Mon, 26 Jun 2000 10:13:10 +0200
Future Beacon wrote:
> Files A and B are composed of the least significant two bits of
> bytes found in news group messages (excluding headers, carriage
> returns, line feeds, and spaces). A and B contain one megabyte
> each of this data. In each case, these bits are strung together,
> four pairs per byte. At least three quarters of the original data
> available in the news group messages is not used.
>
> Then, file B is divided into two files (BP and BQ) this way: If the
> first bit in A is a 0, then the first bit in B becomes the first bit
> in BP. If the first bit in A is a 1, the first bit in B becomes the
> first bit in BQ. In this way, each next bit in A determines whether
> the next bit in B becomes the next bit in BP or BQ. When the bits
> of A and B are exhausted, BQ is appended to BP and the resultant
> file is called RAND.
>
> Two people wishing to send and receive encrypted messages use the
> one-time-pad method but instead of using a random number generator
> to create their shared random numbers, they use the file called
> RAND.
>
> Nobody except these two people know how the news group messages are
> selected and all of the files are kept secret. Does anybody know
> how to attack the encrypted messages? Can anybody characterize the
> degree of orderliness or predictability of RAND (without knowing A
> or B)?
I can't answer your question. But if you want to utilize the entropy in
the stuffs of news groups, I recommend feeding these to a good cipher.
See my article in this group entitled 'On utilizing entropy in natural
language texts' of 19th June.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Announce: Catacomb 2.0.0pre2 now available
Date: 26 Jun 2000 07:58:14 GMT
Mark Wooding <[EMAIL PROTECTED]> wrote:
> 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.
Actually, 2.0.0pre3 is now available. I've just made a portability fix
to that bug fix.
> 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]
------------------------------
** 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
******************************
