Cryptography-Digest Digest #118, Volume #14 Tue, 10 Apr 01 05:13:01 EDT
Contents:
Re: SHA PRNG ("Dobs")
Re: Spam Message Stegano (Frank Gerlach)
Re: Data dependent arcfour via sbox feedback ("Bryan Olson")
Re: Spam Message Stegano ("Douglas A. Gwyn")
Re: question about DES (Francois Grieu)
Re: Patents for Enigma ?? (Frank Gerlach)
Re: p and q for BBS ("Dobs")
Re: p and q for BBS ("Dobs")
Re: Spam Message Stegano (Frank Gerlach)
Re: Steganography with natural texts (Joe H Acker)
NESSIE reports ("Jakob Jonsson")
----------------------------------------------------------------------------
From: "Dobs" <[EMAIL PROTECTED]>
Subject: Re: SHA PRNG
Date: Tue, 10 Apr 2001 09:19:48 +0200
Really????? U could do it for me.It would be really great :))))))))))))))))
It would help me a lot:)))))))))))))))))))
Thanks:))))))))))))))))))))))))))))))))))))))))))
Użytkownik Tom St Denis <[EMAIL PROTECTED]> w wiadomości do grup
dyskusyjnych napisał:mlqA6.66327$[EMAIL PROTECTED]
>
> "Dobs" <[EMAIL PROTECTED]> wrote in message news:9at9qc$25j$[EMAIL PROTECTED]...
> > Perhaps You know where can I find on the web the description of SHA PRNG
> or
> > the source code for it ( I mean not for SHA but SHA prng :) where this
> > algotithm is used :.
> > 1. Make up a random string R and a binary counter C
> > 2. Get T = HASH(R || C)
> > 3. Increment C
> > 4. Output T and goto 2 as required.
>
> I could write this for you in about 15 mins at the most. Let me know if
you
> need me too
>
> Tom
>
>
------------------------------
From: Frank Gerlach <[EMAIL PROTECTED]>
Subject: Re: Spam Message Stegano
Date: Tue, 10 Apr 2001 09:28:23 +0200
Mok-Kong Shen wrote:
> Frank Gerlach wrote:
> >
> > Mok-Kong Shen wrote:
> >
> > > Frank Gerlach wrote:
> > > >
> > > > Should be obvious that you do not even need an Mk1 biological neural net
> > > > to find out this is not a message written by an average english-speaking
> > > > person. A very primitive statistical test will ring the bells...
> > >
> > > Dumb question: What if the writer happens really not to be
> > > a native?
> >
> > That *might* work against an opponent with small resources. Also, your native
> > language should better be neither english, french, german, chinese nor any
> > other major language. On the other hand, using Navajo might also raise
> > suspicions.
> > I guess NSAGCHQ is currently doing a lot of trainung in all kinds of chinese
> > languages :-)
>
> So you believe these agencies are omnipotent, nobody
> could keep anything secret from them.
No, I just think it makes sense to look at the most resourceful opponent.
I am not sure about stegano, but with cryptography there are manual OTP systems in
which I am quite confident that they cannot be broken by the most sophisticated
opponent. Non-OTP crypto and steganography seems to be more of a matter of time
that any method is borken. In other words it is the old cat-and-mouse game. At its
heyday, Enigma was also called "unbreakable". And, it makes sense to think about
the capabilities of the fattest cat in town.
> There are people
> that share you view and resign before attempting to
> protect their privacy. There are others who don't
> share that view. Nobody can prove which party is right,
> I am afraid, much like disputes in religions.
>
> M. K. Shen
------------------------------
From: "nospam"@"nonsuch.org" ("Bryan Olson")
Subject: Re: Data dependent arcfour via sbox feedback
Date: Tue, 10 Apr 2001 07:35:38 GMT
Terry Ritter wrote:
>
>On Sat, 07 Apr 2001 06:24:00 GMT, in <4oyz6.6$4G.143@interramp>, in
>sci.crypt "nospam"@"nonsuch.org" ("Bryan Olson") wrote:
>
>>In article <[EMAIL PROTECTED]>, Terry Ritter wrote:
>>>
>>>On Wed, 04 Apr 2001 19:53:09 -0700, in
>>><[EMAIL PROTECTED]>, in sci.crypt Bryan Olson
>>><[EMAIL PROTECTED]> wrote:
>>>
>>>>Bryan Olson wrote:
>>>>> > Terry Ritter wrote:
>>>>
>>>>> > >The "second data source" is modified by said "result data" before use,
>>>>> > >but no part of the claims excludes that possibility.
>>>>> >
>>>>> > The word "source" excludes the possibility. The sequence of
>>>>> > y values is in fact a _product_ of the substitution process,
>>>>> > not a source. If unclear of the interpretation of "source",
>>>>> > just read the background and look at the diagrams in the
>>>>> > patent.
>>>>
>>>>> Any sequence of data values is "a source." We can see this
>>>>> throughout the patent, including: "A first data source and
>>>>> a second data source are combined into a complex
>>>>> intermediate form or result. . . ." Note the lack of
>>>>> description about the "ultimate" origin of any data sequence
>>>>> treated as a "source."
>>>>
>>>>It may be any sequence of values, but it must be a source,
>>>>not a product. Neither does the ultimate origin matter;
>>>>just that it comes in from the outside.
>>>
>>>The ultimate origin is of course outside *the* *combiner*, but not
>>>necessarily outside the system containing the combiner.
>>
>>The source in question is produced _from_ the table as the
>>"combiner" updates it.
>
>That's fine with me. The Dynamic Substitution claims place no
>limitations on the source of these values.
Right. But it's not a source. It's a product of the same
table.
>>>When you present a system which is more than just the combiner, I am
>>>free to select what signals there are and try to match them to a
>>>claim. You don't get to decide what signals I select. You can add
>>>whatever you want around an invention in an attempt to obscure which
>>>parts actually constitute the invention, but the invention is still
>>>there somewhere, and I get to find it.
>>
>>Exactly. The sequence _you_ chose depends upon the dynamic
>>update of the table. It is necessarily a function of the
>>combiner, and cannot be outside.
>
>I have no idea what your point may be. The claims do not specify a
>particular origin for the sequences.
It's not a combiner of data sources. It's producing one
from state alone.
>>>>> But, if you don't like the word "source," perhaps you would
>>>>> prefer the word "value": [...]
>>>>
>>>>Which is not the word in the claim at issue.
>>>
>>>It only takes one claim. Any claim counts.
>>
>>The one you had cited is claim 1. If you want to instead go
>>through claim 15, note that it's not only a "value" it's an
>>"input value". Claim 15 also states one output, and if you
>>use that value for the output, the cipher cannot function.
>
>I *think* the intent here is to recall an argument made earlier that
>"the cipher" has an XOR combiner, so "the" combiner obviously is not
>DynSub.
Not really. You tried to show claim 1 fit; then when I
argued it didn't, you appealed to the wording of a different
claim.
[...]
>>From "actual words from a claim" to what you are happy with
>>is a huge change.
>
>Fine. So what?
So I said the standard changed and you disagreed. If it's
a "so what" then fine.
>I started out this endless river of text by pointing out that the
>interpretation of an issued patent is a *legal* issue, not a technical
>one, and you responded to that with something deliberately intended to
>have me address the technical issues -- under those conditions.
This is a "sci" group and I'm not interested in armature
lawyering. The legal issues have not even come up. In the
case of recent proposed cipher, no one is using it, or
making or selling any product that includes it. It's a
technically flawed symmetric cipher so doubtless it will
remain unused. In the case of RC4, millions of people use
it and many products include it. Despite some assertions
about trade secrecy years ago, the actions that might raise
legal issues simply do not exist.
>However, not being a patent attorney, not being fully conversant with
>all law, PTO rules, and especially case decisions, I simply cannot
>provide an authoritative interpretation to close calls. The closer
>one gets to trying to be close to DynSub without actually reading on
>the Dynamic Substitution patent, the more risk there will be in any
>technical decision. People can avoid that risk by not trying to use
>Dynamic Substitution without licensing Dynamic Substitution, and it's
>as simple as that.
Agreed.
>>>The body of the patent is used as a dictionary to interpret the
>>>meaning of words used in the claims. I have quoted several times
>>>where it does not support your interpretations.
>>
>>You have quoted such zero times. I never said it couldn't
>>be used to combine confusion sequences, or the various
>>things you cited.
>
>*I* have to follow and respond to -- what? -- 8 or 10 different
>threads, and I am not going to necessarily put every quote in every
>thread. If you don't read all I write, you are going to miss out. If
>you want to keep talking, you have to do at least as much homework as
>me, and you are behind.
Done. (Well, I think so - my news server sucks.) I stand by
my reporting.
>Now, I have thought about this some, and I am now much happier with
>the idea that this is a peculiar and stilted form of Dynamic
>Substitution. That doesn't make it so, that is just my opinion. But
>if somebody really wants to know whether such a design reads on the
>patent, I think it does.
Very well. My opinion differs. Since the proposed cipher
is not likely to see use, that may be as far as we get.
>However, the real purpose of the exercise was for you to present code
>that is almost like some very well known code, and for me to say,
>"Yes, that is Dynamic Substitution," so that you can ridicule anything
>which is that close to what is commonly known.
The purpose was to show that the claims have to "fit" much
more closely than you seem to think. Shuffle doesn't
combine two data sources; it takes just one.
[...]
>>>>> It is implied throughout the patent body that there is no such
>>>>> limitation.
>>>>
>>>>What text from claim 1 implies that? How about claims 2, 7
>>>>and 8? Didn't you also write:
>>>
>>>It doesn't matter. Any one claim counts. It is only necessary for
>>>all aspects of any one claim to be satisfied for a design to read on
>>>the claim.
>>
>>Agreed. But you have no such claim.
>
>Claim 1.
>
>I don't even know what any of this refers to anymore, and I have
>looked back through the quotes and gotten remarkably little help. So
>I *think* this is about whether the claim 1 covers RNG combining and
>maybe also the question of table invertibility.
It refers specifically to a post of yours from April 2.
Here's the "fit" at issue:
>Here's the proposed modified RC4:
>
>byte x, y, z, sbox[256];
>encipher(byte data) {
> x = (x + 1) & 255;
Here x might be the "first data source."
> y = (y + sbox[x]) & 255;
Here y might be the "second data source," and sbox[] might be the
"substitution means for translating values from said first data source
into said result data or substitute value."
The "second data source" is modified by said "result data" before use,
but no part of the claims excludes that possibility. Quite the
contrary, as we see . . . .
The y is not a source; the sequence of values is product of
the table state and cannot be produced outside the combiner.
The x isn't really a source either.
>Much has been said about this on other threads:
>
>First, generally speaking, only the things particularly specified in a
>claim must be present for the design to read on the claim. Here is
>claim 1, yet again:
Using the rest of the patent as a dictionary, we see that
"data source" is used as usual in the description of
algorithms. The "fit" dosn't.
[...]
>Anyone who questions the meaning of terms in the claims is referred
>back to the specification for clarification. With respect to
>combining RNG sources and non-invertible tables, we have:
Exactly.
>"The combiner can also be used to combine two pseudo-random confusion
>streams into a more-complex confusion stream.
How is that relevant? Are you going to say that x, which
steps through the table locations sequential order is a
confusion sequence? There is no confusion sequence there
until it is produced from the table state.
[...]
>"Another use for a dynamic substitution combiner would be to combine
>two different pseudo-random sources. This would generate a
>more-complex pseudo-random combination, and would also help protect
>both input sources from analysis better than the simple exclusive-OR
>combiner generally used. In this case, an extractor would generally
>be unnecessary, since the same combined result could be reproduced by
>generating the original pseudo-random sources and combining them."
>
>"The same mechanism can function with either data or confusion values
>on either input, depending on the goals of the designer. Two confusion
>sources might be combined to make a more complex result, and even two
>data sources might be combined for some reason.
The mechanism here, the stuff inside the section you chose
to match to the claim, is not combining two pseudo-random
source, nor confusion values and plaintext. It's producing
one source from the table state. It is not, and does not
use, the invention disclosed in your patent.
--Bryan
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Spam Message Stegano
Date: Tue, 10 Apr 2001 08:16:22 GMT
Frank Gerlach wrote:
> ... Non-OTP crypto and steganography seems to be more of a matter of
> time that any method is borken.
There are methods for both that really are unbreakable in practice.
But certainly, naive approaches don't have that property.
> At its heyday, Enigma was also called "unbreakable".
Not by anyone competent to judge it.
------------------------------
From: Francois Grieu <[EMAIL PROTECTED]>
Subject: Re: question about DES
Date: Tue, 10 Apr 2001 10:22:37 +0200
newbie <[EMAIL PROTECTED]> wrote:
> Can someone give for every c(i) all elements involved m(i),k(j)
> Is it possible?
The expression of each c(i) can not be expressed as a boolean
function in practice, due to combinatorial explosion: the size of
the expression baloons with the number of rounds
The only feasible expression is built in steps, by defining
each bit of the result of a round as a function of the result
of the previous round and the k(j). Basically, this is
applying the definition of DES.
One thing is for sure: none of the m(i) or k(j) can be eliminated
from the (theoretical) expression of any c(i).
Francois Grieu
------------------------------
From: Frank Gerlach <[EMAIL PROTECTED]>
Subject: Re: Patents for Enigma ??
Date: Tue, 10 Apr 2001 10:33:43 +0200
You think there is any spook with any respect for patents ?
John Savard wrote:
> On Mon, 09 Apr 2001 20:53:45 +0200, Frank Gerlach <[EMAIL PROTECTED]>
> wrote, in part:
>
> >Enigma still "works", and IIRC somebody event got a patent for it. Getting
> >a patent means ZERO.
>
> That patent has expired.
>
> Also, it's true that Germany was in no position to pursue Britain's
> violations of the Enigma patents with respect to the Typex rotor
> machine, but most people who have patents don't live in countries that
> are at war with anyone at the moment.
>
> John Savard
> http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: "Dobs" <[EMAIL PROTECTED]>
Subject: Re: p and q for BBS
Date: Tue, 10 Apr 2001 10:33:50 +0200
Do I understood the idea correct?Should my generation look like this
1. I have to generate big random number, check if it is cogruent 3mod4, if
not generate new random number.
2.Check if it is divisible by first 100 ( or more) primes, if it is
divisible add 8 to it
3 If it is not divisible by this first 100 ( or more) primes than do the
slow test
4. If the number is not prime than add 8 to it , and go to step 2
Am I
right???????????????????????????????????????????????????????????????????????
?????????????????
Użytkownik <[EMAIL PROTECTED]> w wiadomości do grup dyskusyjnych
napisał:[EMAIL PROTECTED]
> "Dobs" <[EMAIL PROTECTED]> writes:
>
> > Blum Blum Shub Generator is said to be slow generator. I implemented BBS
> > Generator using functions from openssl library but it is really slow.
If I
> > want to generate pseudorandom bit sequence which length is lets say 10,
it
> > takes really long time (could even take 10 minutes).
>
> You don't have to generate new p and q every time you want more random
> bits. Just generate your modulus n = p*q once, and save it. Also
> save the x value used in the BBS random generation (x = x^2 mod n) and
> every time you need more bits, use the saved x and n values. Then you
> only need to do the slow prime generation once.
>
> > It has big problem
> > with finding right p and q which should be prime (of course it should be
> > also congruented to 3 mod 4 and be special prime, however it has no
problem
> > with it, it satisfy this 2 condition but it is rarely prime - that is
why it
> > is so slowly)
> > What I am doing is choosing random number ( 512 bits) than checking if
it is
> > prime by Rabin Miller test. If not I add 4 to it and check it one more
> > time. How can I do it in the different way??? I do not want to use
ready
> > function to generate prime numbers( I have to use Rabin Miller test- its
a
> > school task)
>
> Before running your slow test, you should do a fast test for
> divisibility by small numbers up to a few hundred or a few thousand.
> Create a table of the first 100 or so primes, and then check for
> divisibility by these. Only if your value is not divisible by these
> primes do you then do the slow test. This is a big speed-up.
>
> You can also use a "wheel" for iterating. The simplest example skips
> values divisible by 3. You are working with values that are 3 mod 4.
> Every 3rd of these values is divisible by 3. Hence you can alternate
> adding 4 and adding 8, rather than adding 4 each time, thereby
> skipping values that are divisible by 3.
>
------------------------------
From: "Dobs" <[EMAIL PROTECTED]>
Subject: Re: p and q for BBS
Date: Tue, 10 Apr 2001 10:34:17 +0200
In the article 'The Efficient Generation of Cryptographic Confusion
Sequences' was written that:
N is to be the product of two large distinct primes, P and Q. Both P and Q
are to be congruent to 3 mod 4, and must also be special .Prime P is
special if P = 2P1 + 1 and P1 = 2P2 + 1 where P1 and P2 are odd primes
Is it it not true?
I need to built BBS for cryptographic aim. If the only condition would be p
and q- both primes congruemted to 3mod4 would it be still secure BBS which
could be used for cryptographic aims
Użytkownik Tom St Denis <[EMAIL PROTECTED]> w wiadomości do grup
dyskusyjnych napisał:OkqA6.66326$[EMAIL PROTECTED]
>
> "Dobs" <[EMAIL PROTECTED]> wrote in message news:9at9ct$ng$[EMAIL PROTECTED]...
> > Blum Blum Shub Generator is said to be slow generator. I implemented BBS
> > Generator using functions from openssl library but it is really slow.
If
> I
> > want to generate pseudorandom bit sequence which length is lets say 10,
it
> > takes really long time (could even take 10 minutes). It has big problem
> > with finding right p and q which should be prime (of course it should be
> > also congruented to 3 mod 4 and be special prime, however it has no
> problem
> > with it, it satisfy this 2 condition but it is rarely prime - that is
why
> it
> > is so slowly)
> > What I am doing is choosing random number ( 512 bits) than checking if
it
> is
> > prime by Rabin Miller test. If not I add 4 to it and check it one more
> > time. How can I do it in the different way??? I do not want to use
ready
> > function to generate prime numbers( I have to use Rabin Miller test- its
a
> > school task)
> > I take 10 bits of x from every iteration. If I'd liked to generate more
> then
> > 10 bits I have to change change p and q for a new primes and I do not
> want
> > even think how long does it take:(((
> > Please help me!!!
>
> You only need to specify that p and q are prime, and are both congruent to
3
> mod 4. They don't need to be anything else.
>
> Tom
>
>
------------------------------
From: Frank Gerlach <[EMAIL PROTECTED]>
Subject: Re: Spam Message Stegano
Date: Tue, 10 Apr 2001 10:49:06 +0200
"Douglas A. Gwyn" wrote:
>
> > At its heyday, Enigma was also called "unbreakable".
>
> Not by anyone competent to judge it.
Bruce Schneier hints that he doesn't trust in (3)DES. In 2030 he might say
"hey, I told you in 199x..". Until the enormous britsh and american
efforts, both the german and japanese machine ciphers were quite secure.
The same is with DES today. There is just not an army of mathematics
working full-time for years on it.
Enigma was the work of an amateur and it took quite a number of
professionals to break it, whilst DES was conceived by a number of
mathematicians (including the NSA's) over a period of years. Obvious that
the cryptanalysis will take quite a number of the brighest brains for a
couple of years. The mere fact that GCHQ/CESG discovered public-key
crypto FIRST and kept it secret should ring the bells in any sensible
person..
Only that something is in the public does not mean it gets proper review.
Just a few weeks ago some very severe flaws were discovered in a very
crucial part of the Internet Infrastructure (the BIND server). This piece
of source code had been in the public for *years* !
------------------------------
From: [EMAIL PROTECTED] (Joe H Acker)
Subject: Re: Steganography with natural texts
Date: Tue, 10 Apr 2001 10:52:58 +0200
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> > > Consider also an extreme example:
> > > Is there ANY detectable difference for him if, instead
> > > of the sentence 'I met X this morning', I write 'I met
> > > Y this afternoon' (unless he has some guys that follow
> > > me in person)?
> >
> > No, I think in this case there's no difference from a linguistical
> > viewpoint. But of course, a big difference from the extralinguistical
> > viewpoint.
>
> I don't understand what do you mean by 'extralinguistical'
> in the present context.
I was making a kind of joke. The knowledge can be called
extralinguistical because the use of different proper names denoting
*different* persons is not guided by linguistic rules but, of course, by
world-knowledge. The attacker will become very suspicious if he happens
to know that you have met Bob but write that you have met Alice.
>We are arguing whether the
> difference is such as to cause the opponent to 'know'
> that the first sentence is genuine (if he gets the first)
> and that the second is 'artificial' (if he gets the second),
> isn't it?
You have to analyse the data at text level, not at sentence level. Given
just a single sentence, no linguistic methodolgy will detect your
method. The linguist will need several texts from the same speaker(s),
be they steganified or not. And it's good that you've put "know" into
quotation marks because the text- and sociolinguistic methods I refer to
are far from giving any assurance. They merely indicate something or
point to more or less strong assumptions.
> > Hard to say. As you probably know, it's possible to draw conclusions
> > about the origin of a foreign language speaker by examining the errors
> > he makes. This is well researched. But there's unlikely to be any public
> > research about finding out intentional changes made for steganographic
> > purposes.
>
> If I make some typical errors in sentences written out
> directly from my head without my noticing them, wouldn't
> I be likely to make the same kind of errors with much
> the same probability in materials that are 'edited' by
> myself? I mean this problem is not relevant to the
> issue of modification of sentences.
Apart from occasional spelling errors which could be edited by hand,
you're certainly right. I was just giving another example about how
powerful text linguistical methods can be.
As a linguist I felt that it was a good idea to point out how much
linguists can read between the lines and how your method is vulnerable
to linguistic analysis. This work is very complicated and similar to
traffic analysis. All knowledge about the speaker, origin of the texts
and whatever else that seems relevant must be taken into account.
Your assumption that there is not much linguistic data available to the
attacker to me seems unrealistic in practise. Still, you're method has
one *big* advantage over other steganographic methods: While it is
possible to attack it efficiently given enough data, it's almost
impossible to *proof* that a message was hidden because the methods I've
described do not give any proof but just hints. That's a very important
property of good steganography.
But as I've written in another posts, the "synonym channel" does not
have much redundancy and there are better channels like sound or
pictures. I've also written in another thread that a notion of optimal
steganographic encoding can be established information theoretically and
that's what I'm missing about most discussions of steganographic
methods.
Regards,
Erich
------------------------------
From: "Jakob Jonsson" <[EMAIL PROTECTED]>
Subject: NESSIE reports
Date: Tue, 10 Apr 2001 10:56:54 +0200
Public reports of the NESSIE project:
https://www.cosic.esat.kuleuven.ac.be/nessie/reports/
Jakob
------------------------------
** 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
******************************
