Cryptography-Digest Digest #854, Volume #9 Thu, 8 Jul 99 21:13:03 EDT
Contents:
Re: The Constrained One-Time Pad and the Cryptanalyst's Lucky Day
([EMAIL PROTECTED])
Re: Stream Cipher != PRNG ([EMAIL PROTECTED])
Re: I don't trust my sysadmin (Jerry Leichter)
SantaMaria Cipher (wtshaw)
Re: Stream Cipher != PRNG ([EMAIL PROTECTED])
Re: Stream Cipher != PRNG (fungus)
Re: Why this simmetric algorithm is not good? ([EMAIL PROTECTED])
Possible Extension for Block Ciphers ([EMAIL PROTECTED])
Re: Why this simmetric algorithm is not good? (fungus)
Re: Why this simmetric algorithm is not good? (David A Molnar)
Re: Possible Extension for Block Ciphers ([EMAIL PROTECTED])
Re: Stream Cipher != PRNG ([EMAIL PROTECTED])
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Subject: Re: The Constrained One-Time Pad and the Cryptanalyst's Lucky Day
Date: Thu, 08 Jul 1999 22:59:54 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (John Savard) wrote:
> "Tony T. Warnock" <[EMAIL PROTECTED]> wrote, in part:
>
> >Of course the Soviet spies used a super-encypherenment with a OTP
during
> >(and prior to) WWII. The Venona project broke them anyway.
>
> But only because the Soviets did not *really* use an OTP. The NSA
> still doesn't have technology adequate to predicting next week's
> PowerBall numbers, which is essentially the equivalent problem to
> cracking a real OTP, conscientiously used.
>
> They are brilliant minds, with powerful equipment. But miracles are
> beyond even their power.
Maybe a point got missing, but a TRUE OTP can not be broken. Not a
happenning thing. In a implementation bugs or weaknesses might be
available to exploit but this makes them pseudo-otps... It's possible
to guess the message, it's possible that C=P, but that's not a weakness
inherent in OTP.
Tom
--
PGP key is at:
'http://mypage.goplay.com/tomstdenis/key.pgp'.
Free PRNG C++ lib:
'http://mypage.goplay.com/tomstdenis/prng.html'.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Stream Cipher != PRNG
Date: Thu, 08 Jul 1999 22:52:42 GMT
In article <7m39p9$pju$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> Stream ciphers are not the same as PRNGs. We can
> model a PRNG as two functions
> initialize: seed -> state
> generate: state -> (number, state)
>
> We can model a stream cipher as three functions
> initialize: key -> state
> encrypt: (symbol, state) -> (symbol, state)
> decrypt: (symbol, state) -> (symbol, state)
> where
> encrypt(p, x) = (c, y) implies decrypt(c, x) = (p, y)
>
> RC4 is a stream cipher. It uses a PRNG. The output
> of the PRNG is XOR'ed with the plaintext to produce
> the ciphertext.
Yeah but RC4 (in [Sch96]) does not state what mixing function is used.
RC4 is simply a key stream generator. It can be used as a PRNG.
This really isn't conclusive. What makes a stream cipher so different
from a PRNG? Just because the xor? But all stream ciphers are PRNGs
otherwise they would not be secure!
Tom
--
PGP key is at:
'http://mypage.goplay.com/tomstdenis/key.pgp'.
Free PRNG C++ lib:
'http://mypage.goplay.com/tomstdenis/prng.html'.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: Jerry Leichter <[EMAIL PROTECTED]>
Subject: Re: I don't trust my sysadmin
Date: Thu, 08 Jul 1999 18:56:15 -0400
| Re-checking the list today, I note that there is no longer any OS
| listed at the A1 level -- it's almost embarrassing to note that the
| one I mentioned was certified in 1984.
The single A1 system, whose name now escapes, was a tiny thing for a
very old minicomputer system. I believe it was designed and used as
some kind of secure message router. The only reason it had an A1 rating
was that what you had to do to get such a rating changed over the years.
The techniques used to develop and certify it would not have been
acceptable much after it passed - and certainly not today. That's not
to say that it wasn't secure or could not have passed more recent
evaluations - it's just that we don't know, and never will know: An
evaluation is a very expensive process, and no one had any reason to
want to make the investment. (I also gather that the main reason that
system remained on the list for so long was that DoD didn't want the
list to be conspicuously empty. By now, it's perhaps more embarrassing
to have a single 15-year-old system on the list than to have an empty
list.)
| The closest thing to a newer
| version of the same system is from Wang, which has been evaluated at
| B3.
|
| Note that there's not necessarily any difference between B3 and A1 WRT
| the security that's provided -- A1 requires verified design, which
| means the OS design has to be done in a design verification language.
Correct. As of the last time I looked into this stuff, there were no
functional differences between B3 and A1 - the difference was entirely
in the matter of certification.
Just to give you an idea of what "verified design" means: Every piece
of the security kernel has to be described in a formal language, which
is then fed into a theorem prover that has to produce a proof that
certain security properties aren't violated. A friend of mine worked on
such a system (developed at DEC: It was a secure virtual machine
implementation for VAXes, which got canceled when Alpha came out). The
language and the prover were messy and difficult to use. And the proofs
were very sensitive. He tells of one guy in the group who kept
suggesting ways to make the code "better". After one such suggestion,
my friend wrote out the appropriate invariants and ran the prover. He
reported that, indeed, the changes improved the security of the code:
With them in place, he could prove that no one could ever log in!
| IIRC, the NSA has hinted (at least at times) that they'd like to add a
| level above A, in which not only the design, but the implementation
| would be verified as well.
I thought that was what A2 was.
| That might be a bit tough to manage
| though: there's one Scheme system that's undergone formal
| verification. TTBOMK, there's no such thing as a verified
| implementation of anything like C, C++, Ada, or most of the other
| languages in which you'd typically think of implementing an OS.
The DEC implementation was done mainly in PL/I. Ada wasn't available
when the project started (or was rejected for some other reason) and the
other system implementation languages of the time - C and Bliss - were
rejected as hopeless.
The technology to verify an implementation really doesn't exist yet -
verifying the design is near the limits of the state of the art. Note
that NSA and DoD put out deliberate challenges in an attempt to advance
the state of the art. They know they want an A2 system eventually, but
don't expect to see one for years - probably many years.
Note that there *has* been apparently-successful work done on a verified
CPU chip (a couple of years ago, in England). A surprising amount can
be done if you can bound the task (build simple RISC chip; don't try to
build a whole OS, build a virtual machine monitor which interacts with
other OS's, not with users) - and are willing to invest a great deal of
time, manpower, and money. I remember that, after I read Ritchie's
classic Turing award lecture about "trusting trust" - in which he
described inserting what amounted to a security-hole-opening virus into
a C compiler - I asked a friend in the secure computing community how
they could hope to prove any code secure given these kinds of tricks.
His answer was: We examine the machine code. Sure, it's a boring job
that takes a lot of time and manpower - but compared to other expenses,
it's no big deal, and there really is no choice anyway.
-- Jerry
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: SantaMaria Cipher
Date: Thu, 08 Jul 1999 17:14:35 -0600
The SantaMaria Cipher
This cipher has been languishing since March, pending some finishing
touches, and finding an obscure bug, simply solved once I found it
today. Don't you hate it when something works 99% of the time? Best to
clean it up before talking about it; I wish all software manufacturers
were as demanding.
SantaMaria does several things I wanted to do: Make a base translation
cipher with something else than a Base 100 front end, try using three
keys, and produce something with a binary friendly output.
SantaMaria uses base 27 input and base 64 output. Transposition is done
in base 12 information units, doits. Twenty doits, actually represented
by characters, are transposed according to a key. Both bases have their
own substitution keys. Here are the three default keys which represent
350 bits of keyspace:
Sub1(StM): abcdefghijklmnopqrstuvwxyz/
Sub2(StM): abcdefghijklmnopqrstuvwxyzABCDEF
GHIJKLMNOPQRSTUVWXYZ0123456789+/
Trans(StM): abcdefghij klmnopqrst
A full key entry requires 111 characters, but a shorter string might be
used in a pinch to generate all or any one of them. As before, a set of
keys can be transparently entered into the system.
The output is in a familiar format which could used in a scheme to mimic
PGP or MIME, but what you will see here is in common groups. It's just a
matter of juggling the formats around.
I'll use the above paragraph to make a set of keys:
Sub1(StM): /heqywszxivjpafbnkmlctgruod
Sub2(StM): T1qvdreJXChYPjiwIaQfskFlUKGxHyg+
6/LN8795cZV2tbW4M03zDERmnuoOpASB
Trans(StM): fahdeigblj rkmtpncsoq
The same text preformatted comes out as follows in plaintext blocks of 15
characters:
the/output/is/i n/a/familiar/fo rmat/which/coul d/used/in/a/sch
eme/to/mimic/pg p/or/mimej/but/ what/you/will/s ee/here/is/in/c
ommon/groupsx/i ts/just/a/matte r/of/juggling/t he/formats/arou
ndxcompletethegroup
Ciphertext is in groups of 12 characters:
zAntpI0VjkDQ M/P/3MlUjXGX no64cgc6SPPZ n5Vm9KNH7H5h eMUrbfwHMprM
dCEHIIxhj4iz r0sPrz0mRXmv z26vY9warH3Q RN9EYzUGW0Wf OzuZ/GR1lGfx
Vpr3gbU0SuaE yvhvNA/GmHXQ Xm6NRtorJzhR
And, this slightly compressed ciphertext, when recovered and postformatted is:
the output is in a familiar format which could used in a scheme to mimic
pgp or mimej but what you will see here is in common groupsx its just a
matter of juggling the formats aroundxcompletetheg
Since the output is in base 64, readable text, including common
punctuation and spelled digits, can be encrypted with three keys,
representing the equivalent of some 350 bits of keyspace, and further
handled by a bit-oriented algorithm. Needless to say, with DES as a
second stage, lookahead is out of the question for breaking the
two-algorithm chain.
SantaMaria ciphertext could be formatted to look like PGP or MIME.
The name SantaMaria is from latitude and longitude of a place in South America.
--
What's HOT: Honesty, Openness, Truth
What's Not: FUD--fear, uncertainty, doubt
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Stream Cipher != PRNG
Date: Thu, 08 Jul 1999 22:47:09 GMT
[EMAIL PROTECTED] wrote:
> In a private email I was told that stream ciphers and PRNGs are
> completely different beasts. Am I missing something? I always
thought
> Stream ciphers were PRNGs which are difficult to solve (i.e
> intractable).
>
> Can someone please set me straight. RC4 is a stream cipher or PRNG
(or
> both?)
Stream ciphers are not the same as PRNGs. We can
model a PRNG as two functions
initialize: seed -> state
generate: state -> (number, state)
We can model a stream cipher as three functions
initialize: key -> state
encrypt: (symbol, state) -> (symbol, state)
decrypt: (symbol, state) -> (symbol, state)
where
encrypt(p, x) = (c, y) implies decrypt(c, x) = (p, y)
RC4 is a stream cipher. It uses a PRNG. The output
of the PRNG is XOR'ed with the plaintext to produce
the ciphertext.
--Bryan
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: fungus <[EMAIL PROTECTED]>
Subject: Re: Stream Cipher != PRNG
Date: Fri, 09 Jul 1999 02:36:27 +0200
[EMAIL PROTECTED] wrote:
>
> In a private email I was told that stream ciphers and PRNGs are
> completely different beasts. Am I missing something? I always
> thought Stream ciphers were PRNGs which are difficult to solve
> (i.e intractable).
>
Each has different design goals.
A random number generator has to pass statistical tests.
A stream cipher has to have a large "seed" (ie. key), resist
known-plaintext attacks, etc.
> Can someone please set me straight. RC4 is a stream cipher
> or PRNG (or both?) what about SEAL?
>
RC4 has biases when used as a random number generator (try doing
statistics on pairs of output bytes(. These biases don't produce
any cryptographic weaknesses, but may be enough to make it
unacceptable for statistical usage.
--
<\___/>
/ O O \
\_____/ FTB.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Why this simmetric algorithm is not good?
Date: Thu, 08 Jul 1999 22:57:00 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Jerry Coffin) wrote:
> In article <7m2eeh$di7$[EMAIL PROTECTED]>, [EMAIL PROTECTED]
> says...
>
> [ ... ]
>
> [ rewriting ]
>
> > x = (x + 1) & 255
> > y = y + state[x]
>
> [ as ]
>
> > y += state[x = (x + 1) & 255]
>
> [ ... ]
>
> It's open to argument whether it's harder to read, but there's little
> room for argument that with the vast majority of compilers, rewrites
> like this will make absolutely NO difference whatsoever in the object
> code. I'd almost go so far as to say that any compiler that produced
> different object code for these two pieces of code wasn't working
> correctly, but that might be over-stating things a bit.
>
> In any case, a rewrite like this is rarely likely to have any effect
> at all on the size of speed of the object code.
That's not true. Micro-C (low cost embeded C compiler,
www.dunfield.com) will prefer the later because it will keep the value
in the accumulator. It has a optimizer which will optimize the first,
but why?
Most codegens do a good job with the latter, it helps avoid unneeed
load/store operations plus makes good use of the registers.
I prefer the later just because I don't know which compiler will be
used and I would rather have good code on all platforms.
Tom
--
PGP key is at:
'http://mypage.goplay.com/tomstdenis/key.pgp'.
Free PRNG C++ lib:
'http://mypage.goplay.com/tomstdenis/prng.html'.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED]
Subject: Possible Extension for Block Ciphers
Date: Fri, 09 Jul 1999 00:29:05 GMT
Briefly I present CBM Or counter block mode. It's probably not new but
it solves one problem. With a block cipher we know that
C=E(P) and C'=E(P'), if C != C' then P != P'
What if though you used some bytes of the message for a counter
though? It would not reveal the contents of the message. Especially
for large block ciphers (128 bits for example). Basically the message
is about 96 bits and their is a 32-bit counter. You then step thru the
counter for the successive messages. It could be possible to use a
private RNG (LFSR or additive) to make this 32-bit 'quasi-salt'.
In counter mode the cipher would have to be resilient to known
plaintext attacks.
Basically this provides a means for time based permutations (in counter
mode). If you use a PRNG for the counter there is a chance to encode
blocks with the same value...
Just a thought...
Tom
--
PGP key is at:
'http://mypage.goplay.com/tomstdenis/key.pgp'.
Free PRNG C++ lib:
'http://mypage.goplay.com/tomstdenis/prng.html'.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: fungus <[EMAIL PROTECTED]>
Subject: Re: Why this simmetric algorithm is not good?
Date: Fri, 09 Jul 1999 02:32:19 +0200
[EMAIL PROTECTED] wrote:
>
> Well for cleaness and optimizations. Most compilers can optimize lines
> of code if they are companded.
>
> i.e take part of RC4
>
> ---
> x = (x + 1) & 255
> y = y + state[x]
> ---
>
> Can be written as
>
> ---
> y += state[x = (x + 1) & 255]
> ---
>
Rubbish. The compiler will more than likely produce the same
code in both cases. All you achieve by doing this is unreadable
code.
> return state[x = ni[++x]] += state[y = ni[++y]];
>
Code like this would be sent back to you for a rewrite by
many companys.
--
<\___/>
/ O O \
\_____/ FTB.
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Why this simmetric algorithm is not good?
Date: 9 Jul 1999 00:50:02 GMT
[EMAIL PROTECTED] wrote:
> You can always use an extra '&255' if you are not sure, but that makes
> the code slightly longer and slower. Plus almost every platform I have
> worked on uses 8-bit chars. It's kinda a standard (people associate
> chars with ASCII or bytes...)
You're in for a fun surprise when you start writing in Java...
-David
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Possible Extension for Block Ciphers
Date: Fri, 09 Jul 1999 00:34:38 GMT
I forgot to add...
The counter could be 64-bits leaving 64-bits for the message. In this
case each connection would use a different 64-bit counter (say a new
one each day).
You would encode the message as 128-bits, send the bottom 64 bits and
the other user can decode it.
This would add more 'secret' information to link. It's pretty much a
slowly evolving stream cipher. Where many blocks are encrypted at one
time point. You could create a 'key of the week' and use 7 random 64-
bit counters for each day (or some variation). This means that as long
as the keys are not compromised the blocks encrypted are unique for
each day (i.e if C=E(P) for day one and C'=E(P), C != C' but P = P ...)
Has this been proposed before?
Tom
--
PGP key is at:
'http://mypage.goplay.com/tomstdenis/key.pgp'.
Free PRNG C++ lib:
'http://mypage.goplay.com/tomstdenis/prng.html'.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Stream Cipher != PRNG
Date: Fri, 09 Jul 1999 01:03:05 GMT
In article <[EMAIL PROTECTED]>,
fungus <[EMAIL PROTECTED]> wrote:
> Each has different design goals.
>
> A random number generator has to pass statistical tests.
>
> A stream cipher has to have a large "seed" (ie. key), resist
> known-plaintext attacks, etc.
Ideally a stream ciphers key stream should pass statistical tests (well
it should fail to be modeled anyways...)
> RC4 has biases when used as a random number generator (try doing
> statistics on pairs of output bytes(. These biases don't produce
> any cryptographic weaknesses, but may be enough to make it
> unacceptable for statistical usage.
I ran a program which checks based on the previous byte what the next
would be (using an array like this unsigned long prob[256][256]). And
I found for 8MB that I could predict the next byte with a success of
about 1/255, which seems about right.
What type of testing are you talking about? Would you like to see my
code (the test)?
Tom
--
PGP key is at:
'http://mypage.goplay.com/tomstdenis/key.pgp'.
Free PRNG C++ lib:
'http://mypage.goplay.com/tomstdenis/prng.html'.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
** 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
******************************
