Cryptography-Digest Digest #194, Volume #14 Fri, 20 Apr 01 20:13:00 EDT
Contents:
Re: "UNCOBER" = Universal Code Breaker (John Savard)
linear optimization question ("Tom St Denis")
Re: Random and not random (John Savard)
Re: Random and not random ("Mark G Wolf")
Re: digital certs What is the format of the file? ("Joseph Ashwood")
Re: "UNCOBER" = Universal Code Breaker ("Joseph Ashwood")
Re: Delta patching of encrypted data (Benjamin Goldberg)
Re: "UNCOBER" = Universal Code Breaker (Leonard R. Budney)
Re: Delta patching of encrypted data (David Wagner)
Re: Random and not random (newbie)
Re: digital certs What is the format of the file? ("normangrant")
Re: Random and not random (John Savard)
Re: digital certs What is the format of the file? (Paul Rubin)
Re: Random and not random (Matthew Skala)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: "UNCOBER" = Universal Code Breaker
Date: Fri, 20 Apr 2001 21:30:42 GMT
On Fri, 20 Apr 2001 14:58:52 -0300, newbie <[EMAIL PROTECTED]>
wrote, in part:
>How could you know that the keystream used to Xor plaintext is truly
>random?????????
>Truly random is ideal situation. In practice, we measure randomness
>degree. How you measure it????????????
Well, I did note your method would work if randomness was imperfect.
In fact, it's just about what the NSA used in VENONA, where pads were
made by typists trying to make random numbers.
But if you use dice, or pull numbers from a hat, or otherwise use a
physical source of randomness, then you will indeed get numbers that
are close enough to 'truly random' to have no problem with
cryptanalysis.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: linear optimization question
Date: Fri, 20 Apr 2001 21:34:52 GMT
I want to convert a 4x4 matrix into a series of optimal operations (i.e few
as possible). I have gone the otherway with PHT and Multipermutation
networks (i.e go from the ops into the matrix) but I can't figure out how to
go the otherway.
My matrix in question is a 4x4 MDS (I wrote a program to make 4x4 mdses in
GF(2^8)) with coefficients of 1,2 and 3 (i.e 1, x and x+1). It is
02 01 03 01
01 01 02 02
02 03 01 02
01 02 01 03
I would mainly like to know what to look for when trying to make the
operations...(although a full solution would be nice it wouldn't be helpful
since I have to learn how todo this).
My thoughts are to break the thing in half. I.e do the upper left and
bottom right first as the first "layer" then the other corners... but I
dunno if that's meaningful...
--
Tom St Denis
---
http://tomstdenis.home.dhs.org
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Random and not random
Date: Fri, 20 Apr 2001 21:36:50 GMT
On Fri, 20 Apr 2001 15:48:45 -0300, newbie <[EMAIL PROTECTED]>
wrote, in part:
>What do you think about that statement?
Even if it were true (which it shouldn't be) it would let you reject
only such an infinitesimal fraction of possible plaintexts that you
would seldom learn anything at all about the messages you're trying to
read.
In practice, of course, a *serious* military OTP application would
probably work like this:
Plaintext -> conventional cipher -> COTP -> conventional cipher ->
UOTP -> conventional cipher
COTP: constrained one-time-pad; pads consisting of all zeroes, or
which otherwise contain sequences which, by accident, resemble simple
predictable sequences are rejected, so that the input plaintext is
sure to be obscured;
UOTP: unconstrained one-time-pad; every combination of bits is equally
possible, so that the theoretical condition for unbreakability is
fully met.
If you _really_ don't want people reading your mail, it's worth the
extra trouble.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: "Mark G Wolf" <[EMAIL PROTECTED]>
Subject: Re: Random and not random
Date: Fri, 20 Apr 2001 16:53:57 -0500
> COTP: constrained one-time-pad; pads consisting of all zeroes, or
> which otherwise contain sequences which, by accident, resemble simple
> predictable sequences are rejected, so that the input plaintext is
> sure to be obscured;
Please tell me more about this. Wouldn't that just flip all the bits or do
nothing.
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: digital certs What is the format of the file?
Date: Fri, 20 Apr 2001 14:46:42 -0700
Actually you gave the answer, it's an x509 formatted, DER encoded, and you
missed the Base-64 encoded part but it's assumed. As to where to find that
information, the best place I can think of to get it is the source code at
www.openssl.org .
Joe
"normangrant" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Hi
> I have done a few searches of the web for digital certs and find a lot of
> information on how it works etc etc.
>
> The problem is WHAT do you do if you want to write such a file??. Let me
be
> pedantic.. If I wanted to write to a x509 cert DER CA cert, what is the
> exact format needed. I really could not believe that this was not readily
> available on the web!! Thanks
>
>
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: "UNCOBER" = Universal Code Breaker
Date: Fri, 20 Apr 2001 14:51:11 -0700
"Leonard R. Budney" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> "Joseph Ashwood" <[EMAIL PROTECTED]> writes:
>
> > ...in order to be a tRNG it actually MUST fail these very tests on
> > occassion, for reference see by proof by constructing a pRNG that
> > violates the opposing assumption.
>
> That proof doesn't cut it. It proves that a RNG may pass any specified
> set of statistical tests without being a tRNG. It doesn't prove that a
> RNG which passes all the tests is NOT a tRNG.
>
> The proof is quite simple, though. For a tRNG, all sequences are equally
> likely. Therefore, sequences of length N which fail the specified tests
> will happen sometimes. It also seems clear that "sometimes" -> "never"
> as N -> infinity, but (and my ignorance is probably showing) I'm not sure
> how to prove it.
Well you have to start with not trying to prove what can't be proven. A
sequence that passes statistical test, is only valid as a sequence that
passes statistical tests. Because a tRNG will produce all sequences with
equal probability, the probability that a tRNG will pass a statistical test
is exactly the ratio of sequences that pass the test to total sequences of
that length.
Joe
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Delta patching of encrypted data
Date: Fri, 20 Apr 2001 22:04:25 GMT
I've thought a bit more about the problem, and I think I have a
solution. Maybe not the best one, but I think it will work.
F(x,y) --- This can be something like AES_x(y) or H(x||y)... or rather
one byte selected from that. This is your keystream generation
function.
ct[-8..-1] = IV
ct[i] = pt[i] ^ F(k, pt[i-8..i-1]) (for i>0)
Message integity would be done by appending a secure hash (like SHA) of
the plaintext onto the end of the ciphertext. AFAIKS, there is no harm
in encrypting the appended hash, nor any benefit.
This method has one advantage over other enciphering modes, which is a
requirement for being able to patch ciphertext -- no plaintext change
propogates over more than 8 bytes of ciphertext.
This method of encryption has a serious weakness -- if a sufficiently
long sequence of bytes repeats in the plaintext, a repeat is visible in
the ciphertext. Thus, an enemy might be able to construct a sort of
codebook. Unfortunatly, there does not seem to be any way of getting
around this due to the requirement that a "patch" program work on an
encrypted file.
What I can suggest, however, is double-encryption of some sort. Encrypt
with the above, and then encrypt with a second, more secure type of
cipher chaining mode (Perhaps IAPM, with AES as the cipher) -- the
program calling patch will have the key to the outer cipher, but not the
inner one. To patch, decrypt the outer layer of ciphering, then patch,
then reencrypt. There will be short periods of time (when patching) when
the file only has the inner layer of encryption, which a hacker *might*
get access to, but most of the time that the file is on disk, it's
doubly encrypted.
This I think is the best of both worlds. It sits on disk strongly
encrypted. The program calling patch removes that strong encryption
leaving the weak encryption described way up above (not plaintext), and
then after patching re-strongly-encrypts it. Also, there's no reason
that re-enciphering can't use a new IV.
--
Sometimes the journey *is* its own reward--but not when you're trying to
get to the bathroom in time.
------------------------------
From: [EMAIL PROTECTED] (Leonard R. Budney)
Subject: Re: "UNCOBER" = Universal Code Breaker
Date: 20 Apr 2001 18:05:15 -0400
"Joseph Ashwood" <[EMAIL PROTECTED]> writes:
> "Leonard R. Budney" <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > "Joseph Ashwood" <[EMAIL PROTECTED]> writes:
> >
> > > ...in order to be a tRNG it actually MUST fail these very tests on
> > > occassion, for reference see by proof by constructing a pRNG that
> > > violates the opposing assumption.
> >
> > That proof doesn't cut it. It proves that a RNG may pass any specified
> > set of statistical tests without being a tRNG.
(Penny drops) Ah, my statement is exactly what you were saying in the
first place. Namely, "the converse is false". It sounded like your second
statement was intended as a proof of your first statement. Sorry for the
confusion.
> Because a tRNG will produce all sequences with equal probability, the
> probability that a tRNG will pass a statistical test is exactly the
> ratio of sequences that pass the test to total sequences of that length.
I thought I was telling you that.
Len.
--
Frugal Tip #30:
Let a large corporation pay you big bucks to tattoo their company logo
on your bald spot.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Delta patching of encrypted data
Date: 20 Apr 2001 22:12:50 GMT
Benjamin Goldberg wrote:
>ct[-8..-1] = IV
>ct[i] = pt[i] ^ F(k, pt[i-8..i-1]) (for i>0)
FYI, this is sometimes known as plaintext feedback mode (PFB),
and it has the weakness you mention (repeated plaintext blocks
leak information about the text that follows them).
>What I can suggest, however, is double-encryption of some sort. Encrypt
>with the above, and then encrypt with a second, more secure type of
>cipher chaining mode (Perhaps IAPM, with AES as the cipher) -- the
>program calling patch will have the key to the outer cipher, but not the
>inner one.
This doesn't work, because whenever you change a small part of
the document, you have to change almost all of the following
ciphertext to avoid errors due to the outer chaining mode.
------------------------------
From: newbie <[EMAIL PROTECTED]>
Subject: Re: Random and not random
Date: Fri, 20 Apr 2001 18:07:45 -0300
You are right.
I will reject infinitesimal fraction. I made mini-simulation.
So, no way to break it.
I was wrong about randomness.
I'm thinking to try other way.
My way was wrong. I recognize it.
Thank you for all comments.
John Savard wrote:
>
> On Fri, 20 Apr 2001 15:48:45 -0300, newbie <[EMAIL PROTECTED]>
> wrote, in part:
>
> >What do you think about that statement?
>
> Even if it were true (which it shouldn't be) it would let you reject
> only such an infinitesimal fraction of possible plaintexts that you
> would seldom learn anything at all about the messages you're trying to
> read.
>
> In practice, of course, a *serious* military OTP application would
> probably work like this:
>
> Plaintext -> conventional cipher -> COTP -> conventional cipher ->
> UOTP -> conventional cipher
>
> COTP: constrained one-time-pad; pads consisting of all zeroes, or
> which otherwise contain sequences which, by accident, resemble simple
> predictable sequences are rejected, so that the input plaintext is
> sure to be obscured;
>
> UOTP: unconstrained one-time-pad; every combination of bits is equally
> possible, so that the theoretical condition for unbreakability is
> fully met.
>
> If you _really_ don't want people reading your mail, it's worth the
> extra trouble.
>
> John Savard
> http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: "normangrant" <[EMAIL PROTECTED]>
Subject: Re: digital certs What is the format of the file?
Date: Sat, 21 Apr 2001 00:51:40 +0200
I know this may seem like dumb questions, the problem is I want to write a
program in VB where basically it is an idea where our code will look for a
cert, check that the cert has been signed by the CA (Me!!) extract the
public keys and validate the user (all closed environment)... just dont want
to pay verisign every time!!
I have the tools to do the hashing, the key creation etc,( thanks to some
really good stuff I picked up from this site like ebcrypt etc). I simply
cannot understand what the order of the steps are, which are written in
binary/hex/acii etc. I feel really stupid, but I am obviously missing
something
Put another way, when I open up a "known" cert (something with a cer or CRT
extension), I can see a lot of hex etc and obviously can "see" the data, but
I should be able to create such a file in VB if ONLY I could know what I am
looking at in term of which parts of the file is the key, the algorithm etc.
thanks again
"normangrant" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Hi
> I have done a few searches of the web for digital certs and find a lot of
> information on how it works etc etc.
>
> The problem is WHAT do you do if you want to write such a file??. Let me
be
> pedantic.. If I wanted to write to a x509 cert DER CA cert, what is the
> exact format needed. I really could not believe that this was not readily
> available on the web!! Thanks
>
>
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Random and not random
Date: Fri, 20 Apr 2001 22:55:01 GMT
On Fri, 20 Apr 2001 16:53:57 -0500, "Mark G Wolf"
<[EMAIL PROTECTED]> wrote, in part:
>> COTP: constrained one-time-pad; pads consisting of all zeroes, or
>> which otherwise contain sequences which, by accident, resemble simple
>> predictable sequences are rejected, so that the input plaintext is
>> sure to be obscured;
>Please tell me more about this. Wouldn't that just flip all the bits or do
>nothing.
The idea is a COTP is an imperfect one-time-pad. Those pads which do
"just flip all the bits or do nothing" are thrown away and not used.
But those which look like a good set of random numbers are used.
This is not the right way to do a true one-time-pad, yet an opponent
who doesn't _know_ you're using a true OTP might read your message if
you use a 'bad' pad.
So by using both the COTP, and the *true* OTP, or UOTP, plus layers of
conventional encryption, one has better confidence in one's message
being obscured! It is mathematically unbreakable, because a UOTP is
used; it is obscured, because a COTP is used, it is not easily
readable if a breakdown happens in handling the large masses of key
material, because a conventional cipher is used.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Re: digital certs What is the format of the file?
Date: 20 Apr 2001 15:59:53 -0700
"normangrant" <[EMAIL PROTECTED]> writes:
> I know this may seem like dumb questions, the problem is I want to write a
> program in VB where basically it is an idea where our code will look for a
> cert, check that the cert has been signed by the CA (Me!!) extract the
> public keys and validate the user (all closed environment)... just dont want
> to pay verisign every time!!
You could start here:
http://borg.isc.ucsb.edu/aka/auth/ASN1layman.htm
However, you're talking about writing a substantial fraction of an SSL
stack. You're probably much better off using an existing SSL library.
See for example www.openssl.org. It wouldn't surprise me if VB
bindings already exist.
------------------------------
From: [EMAIL PROTECTED] (Matthew Skala)
Subject: Re: Random and not random
Date: 20 Apr 2001 16:39:43 -0700
In article <[EMAIL PROTECTED]>,
John Savard <[EMAIL PROTECTED]> wrote:
>So by using both the COTP, and the *true* OTP, or UOTP, plus layers of
>conventional encryption, one has better confidence in one's message
>being obscured! It is mathematically unbreakable, because a UOTP is
>used; it is obscured, because a COTP is used, it is not easily
>readable if a breakdown happens in handling the large masses of key
>material, because a conventional cipher is used.
I suspect that you know this and are pulling our legs, but:
If there is a chance that the true OTP, used alone, might work out to be
all zeroes, or all ones, and thereby cause the transmitted ciphertext to
accidentally be equal to the plaintext or something from which it is easy
to guess the plaintext, then there is an equal chance that the true OTP,
used along with some other encryption, will work out to be something that
has the effect of undoing all the other encryption and then trivially
encrypting the message.
Theorem: if OTP1(), OTP2(), E1(), and E2() are permutations chosen from
some probability distribution of permutations on the space of all
messages, OTP1(), OTP2() each independent of everything else, and OTP1()
and OTP2() have the perfect secrecy property, and GivesAway(C,P)=1 if and
only if C is a ciphertext from which it is easy to guess plaintext message
P, then for any plaintext message P,
Pr[GivesAway(E2(OTP1(E1(P))),P)=1] = Pr[GivesAway(OTP2(P),P)=1]
i.e. the risk of a bad pad giving away your plaintext for any chain of
encryptions including a true OTP is the same as the similar risk for a
chain of encryptions consisting only of the true OTP.
Proof: Since OTP1() and OTP2() are permutations and have the perfect
secrecy property, all messages are equally probable as their outputs,
regardless of the input message. Thus, OTP1(E1(P)) and OTP2(P) are both
uniformly distributed over the space of messages. Since E2() is a
permutation chosen independently from these, E2(OTP1(E1(P))) is also
uniformly distributed over the space of messages. Then since
E2(OTP1(E1(P))) and OTP2(P) have the same probability distribution, the
theorem follows. []
I believe it would be reasonably simple to make this more general, to
apply to things that are not permutations but still have the perfect
secrecy property. We so rarely talk about such systems, though, that I'm
not going to bother.
The take-home lesson: the risk of possibly choosing a bad pad that reveals
your message is *inextricably* linked to the perfect secrecy property.
You can't have perfect secrecy without that risk, and any attempt to
eliminate it will either fail or destroy the perfect secrecy property.
--
Matthew Skala
[EMAIL PROTECTED] :CVECAT DELENDA EST
http://www.islandnet.com/~mskala/
------------------------------
** 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
******************************
