Cryptography-Digest Digest #116, Volume #9 Sun, 21 Feb 99 10:13:03 EST
Contents:
Re: Another extension to CipherSaber (Paul Rubin)
Re: New high-security 56-bit DES: Less-DES (Bryan Olson)
VxD Crypto - Win 95/98/NT ("R H Braddam")
Re: Testing Algorithms (fungus)
Re: Where to publish hashes? (fungus)
don't waste time on this message [off-topic] (Brainbox)
Re: Bigger variables... (Somny)
Re: Scramdisk File ("hapticz")
Re: Randomness of coin flips (R. Knauer)
Re: True Randomness (R. Knauer)
Re: True Randomness (R. Knauer)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: Another extension to CipherSaber
Date: Sun, 21 Feb 1999 09:05:07 GMT
In article <[EMAIL PROTECTED]>,
Anonymous <[EMAIL PROTECTED]> wrote:
>In December 1998 I built myself a CipherSaber-1 program as per the specs
>on the CipherSaber site (http://ciphersaber.gurus.com). One of the
>suggested non-standard improvements on that website was to add a variable
>number of mixing rounds in the RC4 key initialization phase, so I threw
>this in as an option.
This doesn't seem too useful; it has about the same effect on the
RC4 internal state as doing a single key initialization and then
running the cipher for a while and discarding some output.
>Another improvement I implemented consists of a second number, which I
>call the "discard count." It is a 32-bit value that specifies how many
>cipher bytes to discard before beginning to encipher/decipher. I suppose
>this number is a "key" of sorts as well. It would seem to make the
>searchable keyspace larger by a factor of 2^32, assuming you were choosing
>"discard counts" that used the full span from 0 to 2^32-1.
Discarding some output is considered important to RC4's security, but
making the amount variable complicates things a bit without having any
concrete benefit that I can easily see. Normally one just throws away
256 bytes, which is enough to stir the internal table once.
>Intuitively I cannot see that this weakens CipherSaber in any way.
>Comments? Thoughts?
The main thing I think CipherSaber needs is to produce printable
output for convenient emailing, by coding the output as ascii
characters. Simplest would be to just produce hexadecimal output,
though this doubles the size of the output. A bit nicer would be to
use a 64-character set (like PGP ascii armor) to encode 6 bits/char.
Even fancier is to use 83(?) chars to encode 4 bytes in 5 chars.
Re security, I'd propose increasing the length of the initialization
vector from 10 bytes to maybe 20.
I have a C program called Pcrypt that I think predates CipherSaber
that had about the same motivation; I'll email it on request to US
addresses (it's one file, about 300 lines). But I think a better
language for CipherSaber implementation would be Javascript. Then you
could type your message into a text area field in a web form, your
password into a password box, and click "encrypt" or "decrypt" and the
encryption or decryption would happen in client side Javascript with
the (ascii) output appearing in another text area field or a new
window. Then you could paste the output into your mailer. That way
anyone with a Javascript web browser (even a WebTV) could run
Ciphersaber without having to install any other languages.
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: New high-security 56-bit DES: Less-DES
Date: Sun, 21 Feb 1999 01:59:37 -0800
Ed Gerck, following up my post available at:
http://x7.dejanews.com/[ST_rn=qs]/getdoc.xp?AN=446372808&CONTEXT=919570827.958005461&hitnum=2
wrote:
> In article <[EMAIL PROTECTED]>,
> Bryan Olson <[EMAIL PROTECTED]> wrote: [...]
> > You say that a zero unicity distance would mean a message is known
> > before it's written. Does that mean a unicity distance of 8 means
> > any message is known after the first 8 letters are written?
>
> Yes, but pls exchange "intercepted" for "written" when the unicity > 0,
You had it as "written" when you made the claim for a unicity
(distance) of 0, so I asked if the analogous held for 8. If
you can't answer, fine, but I asked the question I meant.
> and
> do NOT use the word "distance" since it is NOT a "distance" as I have
> commented before and in the paper.
Again I must decline. "Unicity distance" is a term of art in the
discipline. Maybe Shannon could change it, but he retired from the
field a long time ago. When he attended a conference several years
ago, most people there were surprised to learn he's still alive.
In my previous post (linked above) I asked if you think your
definition is equivalent to Shannon's. You snipped the questions.
I'm certainly not going to adopt your terminology in the face of
your refusal to answer.
> My comment that a zero unicity for English
> "would imply that any English message is unambiguously known before being
> even written" is however correct because zero unicity precludes transmission
> or even writing it out as I counter-exemplified -- in other words, if I would
> need to know zero letters from you in order to decipher your message then I
> would not need you to even write anything down, much less send to me.
So you're not even going to address my refutation. What you would
know without intercepting any letters is the key. But you _do_
already know the key since there is only one transformation.
> To be clear, the situation is different for n>0 -- I need to intercept those
> letters. So, I agree that:
Ah, I see. You want to make 0 a special case. See any such special
case in Shannon's definition or his Theorem 7 ?
> So, I agree that:
>
> "A unicity of 8 means that any message is known after the first 8 letters are
> intercepted."
Would you clarify here: if the message is longer than 8 letters, can
the attacker determine plaintext past the part that corresponds to the
intercepted letters? If so, how?
> And ... that is why it is useful -- you know what is the *least* amount of
> letters (8 in this case) that you need to intercept and lug around in your
> attack calculations in order to break the cipher and determine its
> secret-key.
And if there is zero /a priori/ key equivocation, the number of letters
I must intercept to to break the cipher and determine the key is ... ?
> Note however two important points which are often confusing and confused in
> Shannon's approach:
If you find it confusing, please ask. You've no reason to project
your confusion onto others.
> 1. the amount of ambiguity or even obscurity within Shannon's unicity is left
> unspecified.
Just put it in Shannon's precisely defined terms and this confusion
goes away. "Equivocation" quantifies the ambiguity.
> You only know that the attacker cannot decide *what* is the
> correct message -- when the message has a number of letters less than the
> unicity. But, the attacker may have an ambiguity of only 2 messages, with
> zero obscurity (ie, the two possibilities are perfectly discernible and
> intelligible).
Correct! With insufficient text to cover the unicity distance, the
attacker may still get useful information about the plaintext. But
Shannon also covers "perfect secrecy", under which the ciphertext is
independent of the plaintext.
> 2. the amount of work "to know" is also left unspecified in Shannon's
> formalism, which concerns itself with an attacker of unlimited resources --
[...]
Right again, at least until part III of the paper, which is "Practical
Security", and does concern itself with making systems computationally
secure.
It's nice that you know these things, but of course the post you
followed up (see the link at the top) took issue with your startling
original claims. Show that you can recover DES keys given only three
to five intercepted bytes and the crypto world will be amazed. Show
that you understand that theoretical security doesn't consider the
amount of computational work, or that you can break DES with 16
intercepted bytes, a table of trigram frequencies, and exhaustive
search, and we'll think you're posting answers to undergrad homework
assignments.
--Bryan
------------------------------
From: "R H Braddam" <[EMAIL PROTECTED]>
Subject: VxD Crypto - Win 95/98/NT
Date: Sun, 21 Feb 1999 03:47:39 -0600
How to start this? I think everyone reading sci.crypt
(and familiar with Windows) knows about the Windows
swap file possibly leaving sensitive information on
disk, and that memory page locking in application (Ring
3) programs does not prevent pages being swapped to and
from disk even if the pages are locked.
According to the documentation for the Device Drivers
Development Kit for Win 98/NT, page locking works
correctly for Virtual Device Drivers (VxD) and device
drivers (DxD - my own term, if not correct please
advise).
One of the example VxDs in the DDK is Eatpages.VxD. It
grabs and locks half of the available pages at boot-up
and keeps them until shutdown. It is a very simple VxD
and shows how to allocate, lock, unlock, and deallocate
memory. The writer suggests that it could be used to
simulate low memory conditions. It wouldn't work if VxD
page-locked memory was swappable.
Eatpages.VxD could also serve as a starting point for a
secure memory allocator for Crypto functions. A VxD can
map a pointer to its page-locked memory to an
application's address space. A lot is needed to convert
it to a memory allocator and manager, though.
Since allocations and locks are on 4Kb boundaries, I
need efficient methods to manage multiple small
allocations out of a 4K page, and efficient garbage
collection. I have to decide whether to take a
performance hit by dereferenceing pointers through the
VxD or allowing the app to directly access memory. The
OS will not catch illegal accesses for me, so the app
can overwrite memory that does not belong to the
variable referenced by the pointer. My initial tendency
is to give the pointer to the app and let the
programmer debug his/her pointer misuse.
My first inclination is to use two linked lists of
structures (pointer, size, ...) and two chains of pages
to allocate from. One would be for small allocations,
simple variables and structs < 129 bytes, the other for
larger allocations. I'm thinking that this would
concentrate garbage collection better and keep small
allocations from fragmenting memory as much. Another
couple of linked lists would track freed memory for
reallocation. B-Trees might be better than linked
lists. They're actually just a special case of a
doubly-linked list, anyway. Comments?
Secure memory is just the starting point. I intend the
VxD to provide various services like entropy
collection/distillation and PRNG like Yarrow, big
integer/number theory functions, passphrase file
management (username, email addr, encrypted key blob),
and control of algorithms as "devices", among others.
The VxD itself would supply services common to many
different algorithms, and "devices" would provide
specific services like encryption, hashing, key
agreement, etc. The VxD will be written in C and
assembler, while DxDs would be written in assembler.
This is a very ambitious undertaking. The project is
probably too big for me alone. Anyone willing to work
on it with me is welcome. This posting may not draw
much response, but I'm sure my attempts to code the
memory manager will draw criticism and suggestions for
improvement as I post them. Matter of fact, I'm
counting on it.
If this rambles a little (or a lot), it may be because
it is 3:43 am and I got off work at 11:00 PM. Please
forgive me.
--
Rick [EMAIL PROTECTED]
Murphy's Law is the only sure thing in the universe.
------------------------------
From: fungus <[EMAIL PROTECTED]>
Subject: Re: Testing Algorithms
Date: Sun, 21 Feb 1999 22:01:09 +0100
Vegeta-the original Super Saia-jin wrote:
>
> No, in that all forms of cryptography have finite life span and no matter
> how strong they can be defeated in time.
>
> As far as speed goes, the faster the processor the faster the algorithm
>
> As far as security goes, key length helps, but it won't make it secure, I
> think that DES proves that, it's a joke, and a bad one at that.
>
So you think a 256 bit key will eventually be brute forced?
--
<\___/>
/ O O \
\_____/ FTB.
------------------------------
From: fungus <[EMAIL PROTECTED]>
Subject: Re: Where to publish hashes?
Date: Sun, 21 Feb 1999 21:57:26 +0100
lyal collins wrote:
>
> How about a safety deposit box, with 2 person signatures for access, that
> contains either electronic media, printed hashes, or both.
> Lyal
>
... he wanted public access to the signatures.
--
<\___/>
/ O O \
\_____/ FTB.
------------------------------
Date: Sun, 21 Feb 1999 11:29:48 +0000
From: Brainbox <[EMAIL PROTECTED]>
Subject: don't waste time on this message [off-topic]
No-one need pay attention to this message, it's part of my on-going
spam/UCE research (how fast addresses get harvested, etc).
If you're interested I also have a semi-automated "spam complainer" tool
half-finished (and I make no apologies for it being a vb5 program,
mostly cos I can't do C to save my life!). If you'd like to try it,
email mentalmatt{squiggly A thing}bigfoot{d0t}com and I'll send it to
you.
---
How can I be wrong, my modem is error-correcting!
------------------------------
From: Somny <[EMAIL PROTECTED]>
Subject: Re: Bigger variables...
Date: Sun, 21 Feb 1999 03:33:59 -1000
D wrote:
>
> I think that if very secure encryption is necissary, it is simply a
> matter of adding enough key variables. I believe that it is possible to
> describe whole algorithms with keys in some kind of programming language
> thingy. This language would create a variable cipher. This variable cipher
> could be implemented in small operations such as xors, modular
> multiplications, additions, moving bits around, etc. The operations could
> be numbered and indexed. The cipher would require a running keystream and
> would relate to the indicies on the operations, preforming them on the
> current block.
That is similar to the Frog algorithm.
http://www.tecapro.com/aesfrog.htm#b1
This Central American algorithm is a candidate for the Advanced
Encryption Standard selection (AES).
------------------------------
From: "hapticz" <[EMAIL PROTECTED]>
Subject: Re: Scramdisk File
Date: Sun, 21 Feb 1999 09:09:58 -0500
with all that gig space on yer hard drive, why the hay didn't you have a
backup of the scramfile itself? and you actually have customers??
it's time fo ryou to re-evaluate your basic operating procedures, not just
slap on a backup tape unit!!
--
best regards
[EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Randomness of coin flips
Date: Sun, 21 Feb 1999 14:10:50 GMT
Reply-To: [EMAIL PROTECTED]
On Sat, 20 Feb 1999 23:20:52 GMT, "Douglas A. Gwyn" <[EMAIL PROTECTED]>
wrote:
>Maxwell-Boltzmann statistics typify a particular *model*. While
>it is true that there are no *perfectly* ideal gasses, many gasses
>are practically ideal over a vast fraction of phase space attainable
>in laboratories, so the model has great predictive and engineering
>value.
Li & Vitanyi have a different take on that.
>As to unicorns, if one unicorn was definitely spotted then unicorns
>do exist. I think you meant, if *no* unicorn was spotted in a large
>herd, that doesn't mean that unicorns don't exist.
No, I meant what I said, namely that one cannot rule out the
existence of unicorns just because their frequency of occurance
becomes small as more horses are observed.
>> Probability is a theoretical concept, and Kolmogorov among others
>> questioned its applicability to the real world.
>I think you have mischaracterized Kolmogorov's position.
I can cite the very statement by Kolmogorov as it is quoted in Li &
Vitanyi.
>There are certainly issues of how to properly apply probability
>theory, just as there are issues of how to properly apply any theory
>or model. However, many of us successfully apply probability theory
>in our daily work. For example, some of us use it to crack ciphers.
That brings up an interesting point. You are not determinging the
randomness of a number directly when you crack a cipher. You are
applying probability theory in the form on an inferential model (e.g.
Bayes) to discover new information based on information you have at
hand. That is, you are trying to discover regularity, not
irregularity. That's a fundamental difference in how probability
theory is being applied to crypto.
I have proposed several times (and no one has commented thus far) that
one can use probability measures to decide the cryptographic strength
of a TRNG, by using its output to construct many trial ciphers and
then attempt to crack them. If the TRNG produces ciphers that can
withstand many such attacks, or if the ciphers only leak insignificant
amouts of information, then one has experimentally proven that the
TRNG is crypto-grade to within a known level of precision.
Bob Knauer
"If the allegations by Monica Lewinsky are true, if the allegations by Paula
Jones are true, if the allegations by Kathleen Willey are true, and if the
allegations by Juanita Broaddrick are true, then there is a particularly
important resident of Pennsylvania Avenue who needs a lot of professional help."
--Steve Dunleavy, New York Post, 2/20/99
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: True Randomness
Date: Sun, 21 Feb 1999 14:14:30 GMT
Reply-To: [EMAIL PROTECTED]
On Sat, 20 Feb 1999 22:00:56 GMT, "Douglas A. Gwyn" <[EMAIL PROTECTED]>
wrote:
>> Yet a true random number by definition is one which has NO regularity
>> of any kind.
>Thus *your* notion about what constitutes a "true random number"
>is a meaningless "floating abstraction".
Nope - you are in complete error with your statement. I have said many
times on sci.crypt:
+++++
A crypto-grade random number is one produced by a True Random Number
Geberator (TRNG), which is a process that is capable of generating all
possible finite strings equiprobably.
+++++
>Randomness is not a property of individual numbers anyway.
I never said it was.
Bob Knauer
"If the allegations by Monica Lewinsky are true, if the allegations by Paula
Jones are true, if the allegations by Kathleen Willey are true, and if the
allegations by Juanita Broaddrick are true, then there is a particularly
important resident of Pennsylvania Avenue who needs a lot of professional help."
--Steve Dunleavy, New York Post, 2/20/99
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: True Randomness
Date: Sun, 21 Feb 1999 14:24:29 GMT
Reply-To: [EMAIL PROTECTED]
On Sat, 20 Feb 1999 16:35:12 -0800, Michael Sierchio <[EMAIL PROTECTED]>
wrote:
>It depends on the definition of randomness. ONE definition is
>that a number n (represented by a finite bit-string) is "random"
>if it is incompressible -- if there is no binary representation of n
>shorter than floor(lg(n+1)). This is probably what Knauer means
>when he says that it has no regularity.
Nope, that is not what I am saying. I was talking about the generation
process having no pattern. A PRNG has a pattern - the algorithm is the
pattern. A TRNG has no pattern - its process is totally random, like
radioactive decay.
What you are talking about is Kolmogorov Complexity.
>For the purposes of crypto -- OTP or the generation of keys -- I
>will attempt once more to articulate what I believe to be the
>requirements for a random number generator:
>Consider a random bit generator G to be the source of a one-way
>infinite sequence of bits b[0] b[1] .. . We would like the sequence to have
>the following properties:
>1) the behavior of G leads us to expect that all finite strings of
> length n will occur with equal probability (this is a fairly
> strong requirement that will make G pass all of the FIPS-140
> statistical tests, for example);
That conclusion is irrelevant to the definition. The definition of a
TRNG has nothing to do with any statistical tests like FIPS-140.
>2) no finite string (subsequence) b[k] b[k+1] .. b[k+n] of the
> one-way infinite sequence is of any value in predicting b[k+n+1]
> (this requirement eliminates linear and polynomial congruential
> generators and other algorithmic methods);
>3) nothing about the externally-observable behavior of G (e.g.
> consumption of system resources and time) will leak any
> information about the output of G.
#1 is a statement about equidistribution, and #2 is about
independence. #3 is not necessary because it is implied in #2. IOW, if
the TRNG leaked information it would not be behaving in an independent
manner.
Your statements #1 and #2 are completely contained in the definition
of a crypto-grade random number that I have been stating on sci.crypt:
+++++
A crypto-grade random number is one produced by a True Random Number
Geberator (TRNG), which is a process that is capable of generating all
possible finite strings equiprobably [which means independent and
equidistributed].
+++++
The advantage of that definition is that it is much more concise.
Bob Knauer
"If the allegations by Monica Lewinsky are true, if the allegations by Paula
Jones are true, if the allegations by Kathleen Willey are true, and if the
allegations by Juanita Broaddrick are true, then there is a particularly
important resident of Pennsylvania Avenue who needs a lot of professional help."
--Steve Dunleavy, New York Post, 2/20/99
------------------------------
** 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
******************************
