Cryptography-Digest Digest #119, Volume #14 Tue, 10 Apr 01 10:13:00 EDT
Contents:
Re: Steganography with natural texts (Joe H Acker)
Unnecessary operation in DES? ("Brendan Lynskey")
Re: Patents for Enigma ?? (John Savard)
Re: Unnecessary operation in DES? (Matthew Kwan)
Re: Steganography with natural texts (Derek Bell)
Re: Steganography with natural texts (Derek Bell)
Re: approximating addition vs. xor? (Rob Warnock)
Re: latex matrix (Volker Hetzer)
FAQ ("Mis Fazi")
Current best complexity for factoring? ("Tim Gahnstr�m /Bladerman")
Re: Current best complexity for factoring? (Gunnar Andersson)
Re: Virtual English Nation ("Michael Scott")
Re: CA for encryption (Tim Tyler)
Re: Spam Message Stegano (Anonymous)
Re: Self Enforcing Protocol (Slightly OT and Long!) (Jim Farran)
Re: latex quick help (Jonathan Thornburg)
Re: WANTED: Voice Encryption and Telephony Consultant ("Frog2000")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Joe H Acker)
Subject: Re: Steganography with natural texts
Date: Tue, 10 Apr 2001 11:25:24 +0200
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> A stego channel can never be protected against active
> attacks, if I don't err.
I don't think so. An optimal steganographic encoding is immune to any
attack. I'll give you an example (from another post): A radio signal
contains random background noise. You can then use an OTP to hide a
message in the background noise. Please ignore the fact that it's also
"unbreakable" encryption. Just from the steganographic point of view,
the message is completely undetectable without the key. That's a (rather
trivial) sample of an optimal steganographic encoding.
If you think that's because of the OTP, change the background noise to
be non-random. You might still find an optimal steganographic encoding,
namely that encoding whose output has all observable statistical
properties of the non-random background noise.
This can be generalized into a general theory of steganography, but
certainly not by me...
Regards,
Erich
------------------------------
From: "Brendan Lynskey" <[EMAIL PROTECTED]>
Subject: Unnecessary operation in DES?
Date: Tue, 10 Apr 2001 11:36:18 +0100
Hi.
I heard that the first operation in DES involves a shifting bits
independantly of the key.
As the algorithm is public-domain, isn't this step redundant?
And if so why is it in there? I wondered if it was there in order to make
each round more similar, and so to ease implementation.
Any help will be appreciated.
Thanks,
Brendan
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Patents for Enigma ??
Date: Tue, 10 Apr 2001 11:24:26 GMT
On Tue, 10 Apr 2001 10:33:43 +0200, Frank Gerlach
<[EMAIL PROTECTED]> wrote, in part:
>You think there is any spook with any respect for patents ?
But there is a *commercial* market for encryption also.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (Matthew Kwan)
Subject: Re: Unnecessary operation in DES?
Date: 10 Apr 2001 21:32:33 +1000
"Brendan Lynskey" <[EMAIL PROTECTED]> writes:
>I heard that the first operation in DES involves a shifting bits
>independantly of the key.
>As the algorithm is public-domain, isn't this step redundant?
>And if so why is it in there? I wondered if it was there in order to make
>each round more similar, and so to ease implementation.
It adds nothing to security (except, maybe, slowing down brute-force
software key searches), but rumour has it the initial permutation is
there because it simplified the circuit layout in the early hardware
implementations of DES.
mkwan
------------------------------
From: Derek Bell <[EMAIL PROTECTED]>
Subject: Re: Steganography with natural texts
Date: 10 Apr 2001 12:41:15 +0100
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
: Most modern stego schemes are based on embedding bits in
: pictures. A current thread in the group is discussing that.
: I suppose that a competitive way is to embed bits in natural
: language texts. Previously I proposed a method exploiting
: the format freedom of html files. In the following I like
: to present some preliminary thoughts of an alternative,
: though implementationally more expensive, scheme that
: can easily utilize all natural language covertexts, e.g.
: e-mails.
If a situation similar to the mail censorship during
WW2 ever arose this could have problems. There was an incident
where one of the US censors paraphrased a sentence that read
"Father is dead" to read "Father is deceased". The anecdote
says that there was a reply "Is father dead or deceased?".
Derek
--
Derek Bell [EMAIL PROTECTED] |"Usenet is a strange place."
WWW: http://www.maths.tcd.ie/~dbell/index.html| - Dennis M Ritchie,
PGP: http://www.maths.tcd.ie/~dbell/key.asc | 29 July 1999.
|
------------------------------
From: Derek Bell <[EMAIL PROTECTED]>
Subject: Re: Steganography with natural texts
Date: 10 Apr 2001 12:46:32 +0100
Jim Gillogly <[EMAIL PROTECTED]> wrote:
: Hmm -- looks like a proposal with very low throughput. It's
: very difficult to achieve natural-looking text. The opponent
: may not be able to decrypt it, but may be able to detect that
: <something> is wrong.
Yes, the rudimentary statistical models we have in our
minds of the languages we speak seem to be able to detect even
these.
IIRC, it may be more difficult if the code is based on
the number of syllables in a word and there is little ambiguity
as to the number of syllables. (It's been said, in jest,
that Dubliners have an amazing ability to squeeze extra syllables
into a word - e.g. "Dub-lin" vs. "Dub-el-in" in some renditions
of "Molly Malone".)
: Someone -- perhaps Kahn or Pratt -- told a story about censors
: during The War who were responsible for seeing that no
: unauthorized messages got through the telegram office. If
: they saw anything suspicious they would paraphrase it. One
: censor changed "Father is deceased." to "Father is dead."
: Soon across her desk came another telegram. "Please clarify:
: is father dead or deceased?"
It was Kahn, IIRC - I've never read Pratts' book, but
I'm pretty sure it was in _The Codebreakers_.
Derek
--
Derek Bell [EMAIL PROTECTED] |"Usenet is a strange place."
WWW: http://www.maths.tcd.ie/~dbell/index.html| - Dennis M Ritchie,
PGP: http://www.maths.tcd.ie/~dbell/key.asc | 29 July 1999.
|
------------------------------
From: [EMAIL PROTECTED] (Rob Warnock)
Subject: Re: approximating addition vs. xor?
Date: 10 Apr 2001 12:09:17 GMT
Alexis Machado <[EMAIL PROTECTED]> wrote:
+---------------
| S = A + B
| The bit i addition carry ('.' is 'and', '~' is 'not')
| Ci = Ai.Bi or Ai.Ci-1 or Bi.Ci-1
| The bit i addition result
| Si = Ai xor Bi xor Ci-1
+---------------
Slightly off-topic, but this reminds me of the venerable DEC PDP-8
computer (arguably the first "minicomputer"), which had TAD (two's-
complement add), AND, IAC (increment accumulator) and CMA (complement
accumulator, i.e., NOT), but no XOR instruction!! So for doing the
various XORs needed for table-lookup CRC-16 (this was circa 1972 --
CRC-32 wasn't in use yet), we used the following idiom:
/ code to XOR locations A & B, leaving result in AC
CLA / clear AC
TAD A / there is no "LOAD", you have to CLA then TAD
AND B
CLL RLL / clear "LINK" (carry), then rotate LINK||AC left one.
CMA IAC / AC := -AC (two's-compl)
TAD A
TAD B / AC := (A XOR B)
SPOILER: Before reading further, you try to figure it out yourself (or not)...
Here's how it works:
A + B is (A XOR B) + ((A AND B) << 1), right? Well given that, we can
compute A XOR B by calculating A + B - ((A AND B) << 1), or as the
code above does it [to avoid a temp], -((A AND B) << 1) + A + B.
In English: Precompute where the final add is going to place the carries,
take the two's-complement of that, then do a normal add. The carries from
the add cancel with the precomputed negated carries, leaving only the XOR.
-Rob
=====
Rob Warnock, 31-2-510 [EMAIL PROTECTED]
SGI Network Engineering <URL:http://reality.sgi.com/rpw3/>
1600 Amphitheatre Pkwy. Phone: 650-933-1673
Mountain View, CA 94043 PP-ASEL-IA
------------------------------
From: Volker Hetzer <[EMAIL PROTECTED]>
Subject: Re: latex matrix
Date: Tue, 10 Apr 2001 14:33:13 +0200
Tom St Denis wrote:
>
> I am teaching myself latex slowly....
>
> My paper is about 4/12th done ... I need to know how todo multidimensional
> matrices (2x2's and 4x4's...)
You mean a matrix consisting of matrices?
You have to \usepackage{amstex}.
Then you can nest the matrix environment.
Greetings!
Volker
--
They laughed at Galileo. They laughed at Copernicus. They laughed at
Columbus. But remember, they also laughed at Bozo the Clown.
------------------------------
From: "Mis Fazi" <[EMAIL PROTECTED]>
Subject: FAQ
Date: Tue, 10 Apr 2001 14:16:48 +0200
Hi !
Where can I find FAQ?
Michal
------------------------------
From: "Tim Gahnstr�m /Bladerman" <[EMAIL PROTECTED]>
Subject: Current best complexity for factoring?
Date: Tue, 10 Apr 2001 12:28:41 GMT
Hi
I am loosley thinking of algorithms that factor numbers into two primes.
I would like to know the complexity of the best known algorithm for the task
so i have someting to compare with.
I am ofcourse thinking of factoring a number that comes from the
multiplication of two large primes.
Another thing. Are the numbers used in cryptografy usually so big that I
cannot assume that I know al the primes from 1 to the number I am factoring?
Or is that a "valid" asumption?
Thanks alot in advance.
Tim
------------------------------
From: Gunnar Andersson <[EMAIL PROTECTED]>
Subject: Re: Current best complexity for factoring?
Date: Tue, 10 Apr 2001 14:52:18 +0200
On Tue, 10 Apr 2001, Tim Gahnstr�m /Bladerman wrote:
> Hi
> I am loosley thinking of algorithms that factor numbers into two primes.
> I would like to know the complexity of the best known algorithm for the task
> so i have someting to compare with.
> I am ofcourse thinking of factoring a number that comes from the
> multiplication of two large primes.
The general number field sieve has a conjectured complexity of
O(e^(c*(logn)^(1/3)*(loglogn)^(2/3)) for an n-bit number; c is a
constant.
> Another thing. Are the numbers used in cryptografy usually so big
> that I cannot assume that I know al the primes from 1 to the
> number I am factoring? Or is that a "valid" asumption?
Yes.
/ Gunnar
------------------------------
From: "Michael Scott" <[EMAIL PROTECTED]>
Crossposted-To: comp.security.misc,talk.politics.crypto
Subject: Re: Virtual English Nation
Date: Tue, 10 Apr 2001 08:17:27 -0500
>......
> The catholic Irish might be different, though.
>
I love understatement.
Mike Scott
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: CA for encryption
Reply-To: [EMAIL PROTECTED]
Date: Tue, 10 Apr 2001 13:10:43 GMT
Hanna <[EMAIL PROTECTED]> wrote:
: Does anyone ever heard of CA-1.1 ? it use cellular automata for
: encryption/decryption.
Yes: http://www.santafe.edu/~hag/pat/pat.html and
http://www.santafe.edu/~hag/ca11/ca11.html
: What I need to know is, have anyone ever break it ?
I don't know of any results against it at all. I think it may be a bit
too strange for most analysts to tackle ;-)
--
__________
|im |yler Try my latest game - it rockz - http://rockz.co.uk/
------------------------------
From: Anonymous <[EMAIL PROTECTED]>
Subject: Re: Spam Message Stegano
Date: 10 Apr 2001 13:39:07 GMT
>> 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. 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.
"They" ARE omnipotent IF you should happen to come under their scrutiny.
The long-term solution is to raise the amount of encrypted traffic to a level
where They, with all their Crays and all the Mips at their disposal, cannot keep
up. What percentage of communications traffic must be encrypted in order to clog
up their pipes? That's a question I'd like an answer to but will never get receive.
In the short-term cloak yourself as best you can to avoid such scrutiny, perhaps
by using a combination of stego and crypto, being sure to generate plenty of dummy
crypto tarffic for the gang behind the Triple Fence to chew on.
Steve
------------------------------
From: Jim Farran <[EMAIL PROTECTED]>
Subject: Re: Self Enforcing Protocol (Slightly OT and Long!)
Date: Tue, 10 Apr 2001 13:44:54 GMT
Benjamin Goldberg wrote:
> It seems to me that it would be better to explicitly keep track of what
> cards he has in his library.
Your completely right. I was just trying to point out that there is no
reason to keep the contents of the library secret from the owning player
- he could potentially work out what's in there so he might as well be
able to look all the time.
> play, he can get away with it. This may sound unuseful, but it > changes the odds
>significantly.
Again, your right. Since my original post I have extended the protocol,
and I think it can now deal with this. In fact, when playing MTG there
are actually certain limits imposed on what cards can go in the
library. For example, players can only have up to 4 of certain cards in
their deck. I think the protocol can now enforce these constrains,
without revealing the contents of the deck. (I.e. Alice cannot put more
than 4 of a certain card in his deck, but Bob doesn't know how many [if
any] Alice has.
This is even more involved than the last one. As it is symetrical, I
will describe everything from "one side". Alice has a library, a hand
and cards in play. Bob is her opponent.
In this description:
Library = Alice's pile of face down cards. Alice knows what's there,
Bob doesn't. Cards go from library to hand in a random order.
Hand = Cards Alice is holding. Bob doesn't know what's here.
Play = Cards on the table. Alice and Bob can see them.
Deck = Library ++ Hand ++ Play (Fixed throughout game.)
There are c different types of card, each has a different id, in the
range 0..(c-1). Alice can have up to m cards with the same id in her
deck.
There are d cards in Alice's deck. The function D(i) gives the id of
the ith card in Alice's deck.
R is a function which returns a random number.
Protocol:
1. Alice computes M, and reveals the values to Bob:
M(i,j) = Hash(j ++ R(i, j))
For all i in 0<=i<c and j in 0<=j<m.
All values of M must be distinct.
So, we have m different random numbers for each card id. Alice can
reveal the values of M to Bob. Bob cannot work out the values of
R(i,j). But, if Alice later reveals tells Bob a particular i, j and
associated R(i,j), Bob can confirm that this matches a value in M.
What's more, for a particular i, Alice can only reveal m different
R(i,j)s which will match M.
(In looser terms, Alice has chosen m random numbers for each card type.
Bob can't work out what these are. Alice can later reveal up to, but no
more than m of these numbers. Bob can confirm that they are the same as
the numbers she originally chose.)
2. For each card in her deck, Alice must maintain S. Values of S
correspond to cards in her deck. Initially S is defined as follows:
S(i) = R(D(i), j)
Where 0<=i<d
j chosen randomly in the range 0<=j<m. But, if there are multiple cards
with the same id (D(i1)==D(i2), i1!=i2) they must use different js.
(In looser terms, for each card in her deck, Alice finds the type, then
selects one of the m random numbers associated with that card type in
step 1. S(i) the this value concattenated to the card type.)
Each time Alice returns a card to her library, a new random constant is
appended to each S(i). This means that S(i) grows in length each time
this happens, but cards don't go back to libraries very often in this
game.
3. Each time Alice computes a new S, she must also compute a new H and
reveal it to Bob:
H(i) = Hash(D(i) ++ S(i))
4. When Alice plays a card, she reveals D(i) and S(i) to Bob. Bob can
then compute H(i) to confirm that it matches the card he chose.
As R(i,j) is part of S(i), and as Bob knows D(i) he can confirm that
R(i,j) occurs in M exactly once. Because there are only m possible R(i,
j)s for a particular i, this prevents Alice from having more than m of a
particular card in her deck.
Bob can also repeatedly remove the random constants from S(i) and check
this against previous H's to check that Alice has not illegally moved
cards when she shouldn't have.
I hope that all makes sense. I don't think it would to me if I didn't
understand it already. :)
Thanks to the other poster who mentioned "mental poker". That turned
out to be rather useful.
Regards,
Jim
------------------------------
From: [EMAIL PROTECTED] (Jonathan Thornburg)
Subject: Re: latex quick help
Date: 10 Apr 2001 15:57:13 +0200
In article <mxrA6.66513$[EMAIL PROTECTED]>,
Tom St Denis <[EMAIL PROTECTED]> wrote:
>I installed MikTex 2.0 (with the update) I was just wondering if their is
>any quick tutorials on the web how to write tex or more specifically latex
>source files and how to translate them to postscript?
This is sci.crypt. You want comp.text.tex.
--
-- Jonathan Thornburg <[EMAIL PROTECTED]>
http://www.thp.univie.ac.at/~jthorn/home.html
Universitaet Wien (Vienna, Austria) / Institut fuer Theoretische Physik
Q: Only 6 countries have the death penalty for children. Which are they?
A: Congo, Iran, Nigeria, (Pakistan[*]), Saudi Arabia, United States, Yemen
[*] Pakistan reportedly ended it in July 2000. -- Amnesty International
http://www.web.amnesty.org/ai.nsf/index/AMR511392000
------------------------------
From: "Frog2000" <[EMAIL PROTECTED]>
Subject: Re: WANTED: Voice Encryption and Telephony Consultant
Date: Tue, 10 Apr 2001 10:07:29 -0400
--
http://welcome.to/speechsystemsfortheblind
"Paul Rubin" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> [EMAIL PROTECTED] (MrDbol) writes:
> > A client calls 212-333-3333. The call is received, encrypted, and
forwarded to
> > the pre-programmed # in France. The call is then decoded in France and a
secure
> > communication channel is achieved. I would like a system that can handle
100
> > calls at the same time.
> >
> > I am awaiting your response. I need this system implemented asap.
>
> As described, that relies on the US phone system being secure. So
> you're concerned about interception on the French side. Is that
> accurate?
Hmmm....gotta worry about both sides. Unless you just buy your own telephone
lines, and maybe satelites :)
------------------------------
** 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
******************************
