Cryptography-Digest Digest #104, Volume #12 Sun, 25 Jun 00 18:13:01 EDT
Contents:
Re: Compression & Encryption in FISHYLAND (wtshaw)
Re: Linear Feedback Shift Register *with* lock-up? (Chris F Clark)
Re: "And the survey says" ("Paul Pires")
Re: security problem with Win 2000 Encryption File System (Ichinin)
Re: software protection schemes (Ichinin)
Re: Variability of chaining modes of block ciphers (Mok-Kong Shen)
Re: "And the survey says" (David A Molnar)
Re: Variability of chaining modes of block ciphers (Mok-Kong Shen)
Re: Quantum computing (Bill Unruh)
DES and questions (rick2)
Re: Quantum computing (Bill Unruh)
Re: Quantum computing (Bill Unruh)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Compression & Encryption in FISHYLAND
Date: Sun, 25 Jun 2000 11:44:18 -0600
In article <[EMAIL PROTECTED]>, tomstd
<[EMAIL PROTECTED]> wrote:
> [EMAIL PROTECTED] (wtshaw) wrote:
> >In article <[EMAIL PROTECTED]>, tomstd
> ><[EMAIL PROTECTED]> wrote:
> >
> >> Simon Johnson <[EMAIL PROTECTED]>
> wrote:
> >> >Then again, you could always put your differences behind you.
> >> >Rather than trying to slur each other.
> >> >
> >> >I don't know, maybe i'm wrong.
> >> >
> >> >S. Johnson
> >>
> >> Here's something funnier. Some attacks actually work better
> >> against compressed data. The full 16r Differential Attack on
> >> DES for example doesn't work so well with only ASCII plaintext
> >> blocks...
> >>
> >> Anyways...
> >>
> >> Tom
> >>
> >That means that DES was less than universal, but we know that
> already.
> >Imaging that with all other ciphers that ASCII always is the
> best idea
> >uses the same bad emphasis on narrow logic.
>
> I don't follow ya. I never intended to suggest that compression
> will make it weaker, I just wanted to point out an interesting
> observation about how compression can make a cipher stronger
> (which it can't).
>
> Tom
You and I agree about simple compression: It is simple, and adds little at
all to cryptographic strength, but I say that keyed compression may add
some strength that simple compression can't.
David and I have discussed how keying one of his compression routines can
exactly do this, as one must with his implementation load the character
set as a key already. It makes sense, and the edge between crypto and
compression becomes vague.
--
Some Turkeys can fly, for short distances. If you are to depend on
birds for communication, if it's with turkeys, consider the
discussions that might occur while feasting on one.
------------------------------
Crossposted-To: comp.theory,sci.math
From: Chris F Clark <[EMAIL PROTECTED]>
Subject: Re: Linear Feedback Shift Register *with* lock-up?
Date: Sun, 25 Jun 2000 19:14:35 GMT
Ponder wrote:
> I'm looking to use a Linear Feedback Shift Register to implement
> a counter with minimal resources (i.e. fewer gates and wires than
> an additive incrementor).
Trevor L. Jackson, III wrote:
> Assume you have a two-cycle LFSR with periods 1 and 2^N-1, and that
> the singular cycle has the value zero (the classic situation for a
> maximal-period LFSR).
I played around with this a little bit on paper yesterday. I assumed
you were going to implement that LFSR with a set of flip-flops (FFs)
where the output of each FF chained to the next (in a cyclic ring with
the Nth FF chaining to the 1st one) with a little logic to implement
the feedback. I will call the array of FFs a[0] .. a[n].
The 1st LFSR that came to mind was a[i] = a[i] ^ a[i-1] except a[0] =
a[n]--no xor for the loop-around stage. That has some nice
properites. 000... is the 1 period loop. 00001 -> ... -> 1111111 is
the 2**n-1 period loop. Trevor's pattern detector of an and of all
bits works as the saturation detector.
Another LFSR is even more minimal, with a[i] = a[i-1], except a[0] =
a[n] and a[1] = a[0] ^ a[n]. This uses only 1 xor gate. 000... is the
1 period loop and 0001 -> ... -> 100000 is the 2**n-1 period loop.
The saturation detector is almost the same as the previous one, except
all the bits but the high bit are fed in complemented. If you are
doing this on an ASIC with FFs but without ROM cells, I don't think
you can get (much) more minimal.
As to figuring out the values for defining which settings of the FFs
give which counts before looping, it can be done in linear time (with
linear space) if you count operations the same way I do. (It's n**2
if you count them at the bit level.)
Here is some pseudo C-code for it:
int next[n], prev[n], count[n], which[n];
int i, c;
for (i = 0; i < n; ++i) {
next[i] = 0;
prev[i] = 0;
count[i] = 0;
while[i] = 0;
}
// now the values are correct for [0] and initialized for all others
c = n - 1;
for (i = 1; next[i] == 0; i = next[i]) {
next[i] = a[i];
prev[next[i]] = i;
count[i] = c;
while[c] = i;
--c;
}
// now the values are correct for the entire array
// thus, count[i] gives the number of entries before saturation,
// and, which[i] gives the value to pick to be i away from saturation
This works well for LFSR that have two cycles, 1 and 2**n-1. With
another loop or two, one can get a linear algorithm for any FSA's
(with state numbered 0..n) that end with a cycle, even if there are
some elements that are not part of the cycle but only lead into it at
various points.
Hope this helps,
-Chris
*****************************************************************************
Chris Clark Internet : [EMAIL PROTECTED]
Compiler Resources, Inc. Web Site : http://world.std.com/~compres
3 Proctor Street voice : (508) 435-5016
Hopkinton, MA 01748 USA fax : (508) 435-4847 (24 hours)
==============================================================================
------------------------------
From: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Re: "And the survey says"
Date: Sun, 25 Jun 2000 12:35:42 -0700
Scott Fluhrer <[EMAIL PROTECTED]> wrote in message
news:8j5c0i$tr6$[EMAIL PROTECTED]...
>
<Snip>
> Ok, if you want a fantasy list of what properties the perfect symmetric
> cipher would have, how about:
My thanks, As I noted, this thread was an accident but it is something that
facinates me. I am easily amused.
> 1. Provable security. A formal proof that any Turing machine with an
> encryption/decryption constrained [1]oracle, given a ciphertext encrypted
> with a random key, is unable to find the corresponding plaintext with
> probability greater than epsilon in less than (huge number) of steps. Or,
a
> proof of something at least as interesting.
You should probably incude the inability of the attack to determine any
portion of the key with any probability greater than random chance.
But that's cheating! I feel bad enough fantasizing about the Ideal cipher, a
postulated God machine makes even me a little edgy. More to the point, what
would be the attributes of the cipher that make it pass such a test if it
existed?
> 2. Efficiently implementable. It can be done with a minimum of
memory/gates
> on hardware, and any CPU anyone is interested in
Definately.
> 3. Fast. It should be take perhaps 1 cycle per byte encrypted/decrypted
on
> a high end CPU, and not that much slower on low end CPUs. Oh, and it
should
> be blazingly fast in hardware too.
Wouldn't you want to combine #2 and #3 and use a measure of speed per unit
resource used?
> 4. Key agility. There should be no penalty for switching keys.
I'm a little slow. Does this mean that the key is used raw with no hashing,
pre-processing ?
> 5. Build in MAC. The algorithm should have an optional MAC property that,
> if you switch it on, causes minor ciphertext expansion and possibly minor
> slowdown, and has provable forgability resistance.
I notice you said resistance and not immunity. So a probability of 1 in X of
accidentally spoofing it is OK where X is comfortably large?
> 6. Plaintext size. It should be able to encrypt/decrypt any length of
> plaintext, not just those at a particular 'block boundary'.
Ok.
> 7. Ciphertext expansion. Without the MAC feature turned on, there should
be
> no ciphertext expansion.
Does this include extra info for a salt or IV?
> 8. Moderate key size. Key size should not need to be any longer than what
> can be convienently transported using current public-key operations.
> 256-512 bits would be good. I'm willing to make them a bit larger to get
> property #1 (:-)
This is how I see it. Projections of increases in computational ability
have to have a "knee" in the curve considering the short time we have been
collecting data points. 512 bits has a comfortable feel based on my biases.
How about a characteristic that speed or resources used should be a linear
effect of key size and not exponential. I think this ties in with #2 and #3
above.
> Now, obviously, no known cipher has all, or even most, of these
properties.
> 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). Those
> ciphers that do fufill (or at least come close to fufulling) a subset of
> these properties have other drawbacks that make them inapplicable to other
> applications. In other words: you need to select the appropriate cipher
for
> the application.
Hey, since we're dreaming, why not throw in resistance to known plaintexts
of a number below that produced during the maximum life of the key used?
> I'll let others decide whether all the items on the list are relevant
> (although, I believe every item is useful for some application), or there
> are other items that should be on the list. And, I'll let others list how
> various ciphers come close to meeting items on this list.
>
>
> [1] The constraint on the Oracle is that you can't ask the decryption of
the
> input ciphertext.
>
>
> --
> poncho
And back to the beginning. I enjoy cipher design but it seems that there is
no *reason* to do it other than self-satisfaction. It seems that all of the
pieces are laying around for an encryption oracle suitable for any
application but the goal of a general purpose cipher with a good score
across the board might still be needed.
Thanks for your time.
Paul
------------------------------
From: Ichinin <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: security problem with Win 2000 Encryption File System
Date: Sun, 25 Jun 2000 22:00:34 +0200
Paul Rubin wrote:
> If the boot sector is encrypted, how can you boot?!
**** Normal bootloaders work this way: ****
<Bootsector> (Linux, MSDos... you name it)
-> Call IO.SYS (A.s.o)
**** Encrypted work in this way: ****
<Decryption-Bootsector>
-> Require password (or other items)
-> Decrypt the encrypted "virtual bootsector" to memory.
-> Boot from that.
A PC is just DUMB hardware that requires a program to run from, Where
that program resides (CDRom, Memory, Harddrive) is of no importance: The
computer just executes the instructions (if those instructions say,
access the IDE interface and starts reading, then you have a bootloader,
not a bootsector, 2 words, 2 ways - same result..)
/Ichinin
------------------------------
From: Ichinin <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: software protection schemes
Date: Sun, 25 Jun 2000 22:22:39 +0200
lament wrote:
> Given that billions of instructions transpire, how do you know which one(s) are the
> one?
When i neutralised cp'ed programs in the 80's, i ran programs that
checked what IO calls
were made, what files did it access? etc. You can also exclude alot of
stuff by logical
exclusion alone; say if the program starts, requires you to
authenticate, and the CDRom
is not in the computer then the copy proection must reside on the
installed files on the
system. Kill a file, retry untill you cannot remove any more files.
Besides, you can always decompile stuff in a virtual environment, where
whatever security
precautions you have set - will fail. Tough luck...
> The CAD industry uses dongles.
The car industry put airbags in cars, still people die on the road.
So..?
Do the software RESIDE on the dongle? Then it would be "uncopyable"
untill
someone would extract the program from the hardware. At runtime, the
software STILL
would need to run INSIDE your computer and everything would fail anyway.
Even IF
you could protect your hardware against runtime debuggers, you could
still attack
it at no-runtime.
(P.S: What do the CAD industry know of making secure protocols?)
> I guess this depends on what you mean by "good," "reliable" and "a myth."
You've never pulled up a disassembler or a hex editor and cracked a
game, have you?
Ichinin
(Ex-80's games/code cracker)
Sweden
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Variability of chaining modes of block ciphers
Date: Sun, 25 Jun 2000 23:15:33 +0200
Tim Tyler schrieb:
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> : Tim Tyler wrote:
> :> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> :> : Eric Lee Green wrote:
> :> :> Mok-Kong Shen wrote:
>
> :> :> > [...] By combinatorics this gives 8 variants.
> :> :>
> :> :> Great. You just added 3 bits to the key space [snip at what expense]
> :>
> :> : If you use CBC, then switching to PCBC (using both plaintext and
> :> : ciphertext) may result in a difference more than what can easily be
> :> : quantified by bits.
> :>
> :> Why can't the attacker just split his resources and attack both ways?
> :> Using one of two types of chaining mode won't add more than 1 bit to the
> :> keyspace.
>
> : If, in doing a little thing, you could cause your (mighty) opponent to
> : split his resources, isn't that something that well deserves your
> : consideration?
>
> Why, certainly.
>
> I've a feeling you might need to make some things on this thread more
> concrete before they can be debated properly.
>
> For example, can you present a class of chaining modes which
> you think are immune to David Hopwood(?)'s criticism that an attacker may
> sometimes be able to recover the chaining mode used in some types of
> chosen plaintext attack, by flipping bits and watching the results.
>
> Do you think large classes of such chaining modes exist, so the security
> benefit is more than just a few bits of keyspace?
I personally prefer chaining using both accumulated plaintext and
accumulated ciphertext (xor or addition mod 2^n). One can use
two IVs that are secret. If these are independent of the key of the
cipher, the scheme certainly adds more than a few bits of keyspace
in my view.
M. K. Shen
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: "And the survey says"
Date: 25 Jun 2000 21:15:23 GMT
Paul Pires <[EMAIL PROTECTED]> wrote:
> Scott Fluhrer <[EMAIL PROTECTED]> wrote in message
> news:8j5c0i$tr6$[EMAIL PROTECTED]...
>>
>> 1. Provable security. A formal proof that any Turing machine with an
>> encryption/decryption constrained [1]oracle, given a ciphertext encrypted
>> with a random key, is unable to find the corresponding plaintext with
>> probability greater than epsilon in less than (huge number) of steps. Or,
> a
>> proof of something at least as interesting.
> You should probably incude the inability of the attack to determine any
> portion of the key with any probability greater than random chance.
well, first of all, you care about the message, not about the key. right?
In a previous thread here, someone (my apologies, cannot remember who)
pointed out LION and BEAR as examples of schemes where you could prove
that the key could never be recovered from the ciphertext...but where
the cipher turned out to be an identity permutation for some keys and
some plaintexts.
second, you should also maybe consider a cipher where even if you DO know
part of the key, it does not help you any more than cutting down on your
guessing time.
(question of the moment : is this notion of "no help from partial key
exposure" implied by semantic security? my guess would be no, because
you can take any semantically secure cryptosystem C and create a C'
which uses only the first half of the key or something like that).
> But that's cheating! I feel bad enough fantasizing about the Ideal cipher, a
> postulated God machine makes even me a little edgy. More to the point, what
> would be the attributes of the cipher that make it pass such a test if it
> existed?
The thing is, we *have* public-key ciphers which *do* satisfy those
kinds of definitions, subject to the major caveat that we have a
trapdoor one-way function. The definitions are so "strong" because
they are trying to capture all the chosen plaintext and chosen ciphertext
attacks which anyone could ever think of. Yes, it's a "God Machine,"
but only because our adversary must be considered as next to God if
we are not to fall into the trap of underestimation.
RSA with Optimal Asymmetric Encryption Padding
is an "almost"-example of such a system. I say "almost" because the
proof uses "random oracles" and so is not considered by some to be
totally kosher (I can expand on that if anyone wants, but it's a tangent).
A better example would be the Cramer-Shoup system from Crypto '98,
which they managed to show is "secure" in the kind of sense given above
if and only if the "decision diffie hellman problem" is hard.
Such ciphers tend to be randomized. Encrypting involves not only the key,
but some random bits as well to make the output look more random.
This requires a better treatment that I don't ahve time to write
right now. You can try looking at Bellare & Goldwasser's lecture notes
and/or Goldreich's fragments of a chapter on encryption schemes to
see some of the flavor of the ciphers which satisfy these definitions.
Also the Optimal Asymmetric Encryption Padding paper.
check http://www-cse.ucsd.edu/users/mihir/
and http://theory.lcs.mit.edu/~oded/
and follow the publication links.
There's a lot of work that I know of on building public-key randomized
cryptosystems, but I don't know of that much on building randomized
symmetric ciphers...maybe because the people working in each area do not
seem to overlap very much.
Jon Katz and Moti Yung had a neat paper in the last STOC on what
definitions of security for symmetric cryptography would look like.
I don't have it on me now, but looking at it might be instructive.
-dmolnar
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Variability of chaining modes of block ciphers
Date: Sun, 25 Jun 2000 23:39:29 +0200
Mok-Kong Shen wrote:
> I personally prefer chaining using both accumulated plaintext and
> accumulated ciphertext (xor or addition mod 2^n). One can use
> two IVs that are secret. If these are independent of the key of the
> cipher, the scheme certainly adds more than a few bits of keyspace
> in my view.
Addendum:
The method of chaining I described was implemented in my
algorithm WEAK3-EX. I personally don't like the common CBC,
since all the chaining values are known to the analyst.
(Often a plain IV is used. Using a secret IV in this case
renders only the chaining value of the first block unknown
to him.)
There can also be other chaning modes than what I mentioned
in my original post.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: Quantum computing
Date: 25 Jun 2000 21:55:12 GMT
In <[EMAIL PROTECTED]> "Douglas A. Gwyn" <[EMAIL PROTECTED]> writes:
][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 have no idea at all of what is involved with building a quantum
computer with an internal memory of more than say 10 bits.
------------------------------
From: rick2 <[EMAIL PROTECTED]>
Subject: DES and questions
Date: Sun, 25 Jun 2000 21:57:35 GMT
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?
2. I think it would also be convenient for the user to have some sort
of a check when they enter the password, to alert them if they made
a mistake, but obviously I don't want to store the real password in
their data file. How can I do this without compromising the security
too much? Would it be acceptable to simply add up all the characters
in the password and then save that as a single byte "checksum" of
the password? I guess that would reduce the security, but by how much
(like maybe by 8 bits worth, if that is a measure of security?)
Would it be better to save a stronger type of hash of the password, or
would that also not really help the security either? I think I only
need to save 8 bits because it's OK with me if they make an error
that isn't rejected 1 out of 256 times...
Thanks!
Rick
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: Quantum computing
Date: 25 Jun 2000 21:59:16 GMT
In <[EMAIL PROTECTED]> Dido Sevilla <[EMAIL PROTECTED]> writes:
]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
We do not have anything that anyone but a pedant would call a quantum
computer. Something with a maximum memory of 5 bits is not a quantum
computer in any meaningful sense of the word. Such a "computer" can be
simulated on my Pentium far far far faster thanit can solve any problem.
]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...
And none of the ideas scale, so that what is done now is no help in
building something that might actually be useful. Haroche, working with
light traps, claims each bit represents about 2 years work ( and they
are up to about 3 or 4 bits now).
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: Quantum computing
Date: 25 Jun 2000 22:01:02 GMT
In <[EMAIL PROTECTED]> "Douglas A. Gwyn" <[EMAIL PROTECTED]> writes:
>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.
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.
------------------------------
** 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
******************************
