Cryptography-Digest Digest #367, Volume #13 Tue, 19 Dec 00 20:13:00 EST
Contents:
Re: Q: Result of an old thread? (Simon Best)
Re: Q: Result of an old thread? (Simon Best)
Re: Steganography using text as carrier (Andre van Straaten)
Re: Homebrew Block Cipher: Moonshine (Simon Best)
Re: Q: Result of an old thread? (Bryan Olson)
Re: SMS security over various networks? (Gregory G Rose)
Re: does CA need the proof of acceptance of key binding ? (Thierry Moreau)
Re: Steganography using text as carrier (Andre van Straaten)
----------------------------------------------------------------------------
From: Simon Best <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Q: Result of an old thread?
Date: Tue, 19 Dec 2000 23:50:04 +0000
I'll leave this unsnipped, for easy reference when I finish off:
Mok-Kong Shen wrote:
>
> Simon Best wrote:
> >
>
> > (I'll mention here that I'll use multiplications to get relevant
> > results, rather than inversions with multiplications, as the
> > multiplications are enough to show it, and I'm too rusty on inversions!)
> >
> > S = A = B=
> > [ S0,0 0 ] [ A0,0 A0,1 ] [ B0,0 B0,1 ]
> > [ S1,0 0 ] [ A1,0 A1,1 ] [ B1,0 B1,1 ]
> >
> > So...
> >
> > AS =
> > [ A0,0 A0,1 ][ S0,0 0 ]
> > [ A1,0 A1,1 ][ S1,0 0 ]
> > =
> > [ (A0,0)(S0,0)+(A0,1)(S1,0) 0 ]
> > [ (A1,0)(S0,0)+(A1,1)(S1,0) 0 ]
> >
> > which I'll type as:
> >
> > AS =
> > [ AS0,0 0 ]
> > [ AS1,0 0 ]
> >
> > for the time being.
> >
> > Then...
> >
> > ASB =
> > [ AS0,0 0 ][ B0,0 B0,1 ]
> > [ AS1,0 0 ][ B1,0 B1,1 ]
> > =
> > [ (AS0,0)(B0,0) (AS0,0)(B0,1) ]
> > [ (AS1,0)(B0,0) (AS1,0)(B0,1) ]
> >
> > Notice that ASB is independent of B1,0 and B1,1! The second row of B
> > plays no part in producing ASB. This is very important, as this is the
> > only opportunity B gets to add its elements to the encryption, but its
> > bottom row plays no part. What's more, if we define:
> >
> > AS' = B' =
> > [ AS0,0 ] [ B0,0 B0,1 ]
> > [ AS1,0 ]
> >
> > by chopping out the empty column of AS and the corresponding row of B,
> > then we can do:
> >
> > ASB' =
> > [ AS0,0 ][ B0,0 B0,1 ]
> > [ AS1,0 ]
> > =
> > [ (AS0,0)(B0,0) (AS0,0)(B0,1) ]
> > [ (AS1,0)(B0,0) (AS1,0)(B0,1) ]
> > = ASB
> >
> > Let's now consider some matrix S', which is identical to S except that
> > it's got the empty columns left out:
> >
> > S' = A =
> > [ S0,0 ] [ A0,0 A0,1 ]
> > [ S1,0 ] [ A1,0 A1,1 ]
> >
> > A(S') =
> > [ (A0,0)(S0,0)+(A0,1)(S1,0) ]
> > [ (A1,0)(S0,0)+(A1,1)(S1,0) ]
> > =
> > [ AS0,0 ]
> > [ AS1,0 ]
> > = AS'
> >
> > So, the AS' that I've trivially obtained from AS is what AS would have
> > been if S had not had those empty columns in in the first place.
> > Furthermore, my ASB' is what ASB would have been if B had not included
> > the rows discarded by the empty columns in AS.
> >
> > The important thing here is that AS' is invertible, and can trivially be
> > used to derive a matrix B'. B' will just be B without the discarded
> > rows. Is that enough to get S from SB? Looking at SB in terms of S and
> > B:
> >
> > S = B =
> > [ S0,0 0 ] [ B0,0 B0,1 ]
> > [ S1,0 0 ] [ B1,0 B1,1 ]
> >
> > SB =
> > [ (S0,0)(B0,0) (S0,0)(B0,1) ]
> > [ (S1,0)(B0,0) (S1,0)(B0,1) ]
> >
> > Again, the bottom row of B is discarded. Comparing with using B':
> >
> > S' = B' =
> > [ S0,0 ] [ B0,0 B0,1 ]
> > [ S1,0 ]
> >
> > S'B' =
> > [ (S0,0)(B0,0) (S0,0)(B0,1) ]
> > [ (S1,0)(B0,0) (S1,0)(B0,1) ]
> > = SB
> >
> > Now, is B' invertible? It certainly looks like it! Can the inverse of
> > B' be used with SB to get S? It's certainly looking that way! After
> > all, SB is both the product of S with B and S' with B', and S' contains
> > the whole message!
> >
> > This method can be applied to larger matrices. The important thing is
> > that the empty columns of S just end up effectively discarding rows of B
> > and other matrices, such that the whole thing's equivalent to not
> > bothering with empty columns in S in the first place. Those empty
> > columns don't add any security after all, and the system is trivially
> > defeated.
> >
> > So, is there any reason why this method would not work?
>
> Sorry, I have difficulty to follow you. Your AS' is a vector not a matrix.
It is a matrix. It doesn't fail to be a matrix just because it's got a
single column (that's basic stuff!). Anyway, it came out as a single
column matrix above because I was illustrating with small matrices. It
doesn't matter, though.
> How can that be invertible?
Oh, alright, I was being sloppy and lazy, and didn't check that basic
stuff myself! (I'm very, very rusty...) What's wanted is some way to
effectively undo a multiplication of AS' and B'. I wanted to get B'
from AS' and ASB...
AS' * B' = ASB
That's the equation I need to satisfy. I've already got AS' from AS by
chopping off the empty column in AS, and I've already shown that AS' *
B' = ASB, where B' would just be B without the empty row. It's a matter
of finding B'...
[ AS0,0 ][ B0,0 B0,1 ] = [ ASB0,0 ASB0,1 ]
[ AS1,0 ] = [ ASB1,0 ASB1,1 ]
Obviously:
ASB0,0 = (AS0,0)(B0,0)
ASB0,1 = (AS0,0)(B0,1)
ASB1,0 = (AS1,0)(B0,0)
ASB1,1 = (AS1,0)(B0,1)
Four, simultaneous equations, with only two unknowns, B0,0 and B0,1.
It's really simple:
B0,0 = (ASB0,0)/(AS0,0) = (ASB1,0)/(AS1,0)
B0,1 = (ASB0,1)/(AS0,0) = (ASB1,1)/(AS1,0)
B' =
[ (ASB0,0)/(AS0,0) (ASB0,1)/(AS0,0) ]
So I've now got B', and can make use of that with SB:
S' * B' = SB
[ S0,0 ][ B0,0 B0,1 ] = [ SB0,0 SB0,1 ]
[ S1,0 ] [ SB1,0 SB1,1 ]
Again, I've got to find S' from B' and SB:
SB0,0 = (S0,0)(B0,0)
SB0,1 = (S0,0)(B0,1)
SB1,0 = (S1,0)(B0,0)
SB1,1 = (S1,0)(B0,1)
Again, four simultaneous equations and only two unknowns, S0,0 and S1,0:
S0,0 = (SB0,0)/(B0,0) = (SB0,1)/(B0,1)
S1,0 = (SB1,0)/(B0,0) = (SB1,1)/(B0,1)
And I've got the secret message!
> And the (trivial) derivation of B' is also not given, I suppose.
It seemed too trivial (which it was, as you've now seen, though with
simultaneous equations rather than inverting matrices (but that didn't
matter in the end)). I was just presenting how it ends up being trivial
problem.
> Could you work out a numerical example? Thanks.
>
> M. K. Shen
Would you like me to understand the numerical example for you, too? If
you want a numerical example, you can always put numbers in yourself,
and see where it takes you. But since you ask:
AS =
[ 1051 0 ]
[ 910 0 ]
ASB =
[ 22071 19969 ]
[ 19110 17290 ]
SB =
[ 609 551 ]
[ 378 342 ]
(All three matrices are singular.) I've derived those matrices from a
secret A, secret B, and secret S. One thing I'll say about S is that it
has an empty column, and it's the right hand column that's empty, so
that it's just like in my stuff above. A, B and S are all 2x2 matrices,
and have integer elements.
Now, do the following:
1. Get AS' from AS. (Chop out the empty column.)
2. Get B' from AS' * B' = ASB. (Trivial simultaneous equations.)
3. Get S' from S' * B' = SB. (Trivial simultaneous equations.)
What did you get for S'?
Simon
--
_______________________________________________________________________________
Personal: [EMAIL PROTECTED]
Yellow Skies: [EMAIL PROTECTED] http://www.yellowskies.com
Everyone does their own signature to be different. How does that work?
------------------------------
From: Simon Best <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Q: Result of an old thread?
Date: Wed, 20 Dec 2000 00:01:49 +0000
Mok-Kong Shen wrote:
[...]
> You misunderstood me. The cipher in question has never
> been formally analysed, otherwise we wouldn't be discussing
> it here. I was alluding to the analogy of block ciphers,
> where a neat claim of its strength/weakness needs to give
> the quantity of amount of work to break it with respect
> to a given technique.
>
> M. K. Shen
Erm, okay. Why not do some analysis and post it here? You could even
just try out some of the suggestions already posted by others. You
know, plug in some numbers and see if they work or not...
(I'm about to move on to analysing integer element matrices with a
singular S that doesn't have any empty columns (or rows).)
Simon
--
_______________________________________________________________________________
Personal: [EMAIL PROTECTED]
Yellow Skies: [EMAIL PROTECTED] http://www.yellowskies.com
Everyone does their own signature to be different. How does that work?
------------------------------
From: Andre van Straaten <[EMAIL PROTECTED]>
Subject: Re: Steganography using text as carrier
Date: 19 Dec 2000 18:10:02 -0600
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> [EMAIL PROTECTED] wrote:
>>
> [snip]
>>
>> is there a way to hide already encrypted messages (ciphertext block)
>> within a *text* carrier,(not within the whitespace) and if so, what are
>> the size constraints of ciphertext to carrier text?
>>
>> as redundancy would not be particularly surprising in spam messages,
>> this might be a promising new avenue for effective steganography.
> Steganography is very much an art in my humble view. I
> don't think that there is any algorithm (automatic means)
> of doing the job you described, though there are methods
> of hiding bits in pixels etc. (A number of proceedings
> on information hiding have been published by Springer
> Verlag from which more pointers could be obtained.)
> M. K. Shen
I remember the obvious modifications of one steganographic tool
to .bmp files. This example has been brought just by the OP of
this thread.
I had no further search on that topic, but I'm pretty sure that
scrutinizing the altered files by analyzing and comparing the
distribution of bits lets detect all sorts of steganography files
unless you hide very little information or you use a special kind
of graphics for that purpose.
I think, good steganography must resist sophisticated methods and
not only a superficial comparison by the human eye.
In this sense, I can imagine some algorithms to hide information
inside of text, but I see problems to transmit a larger amount of
information frequently, as it is no problem with most crypto
tools.
Another disadvantage, is that the traffic of messages itself has
to be undistinguishable from normal behavior.
There are size, sort of, frequency, and addressee of the message.
-- avs
Andre van Straaten
http://www.vanstraatensoft.com
The signs and the omens are everywhere
But too few see them - too few even care
(Lee Clayton - singer/songwriter, 1979)
====== Posted via Newsfeeds.Com, Uncensored Usenet News ======
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
======= Over 80,000 Newsgroups = 16 Different Servers! ======
------------------------------
From: Simon Best <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Homebrew Block Cipher: Moonshine
Date: Wed, 20 Dec 2000 00:21:18 +0000
Tim Tyler wrote:
>
> Tom St Denis <[EMAIL PROTECTED]> wrote:
>
> : Why do you feel that a Feistel is bad?
>
> Here's my (simplistic) perspective of what's wrong with Feistel networks:
>
> Feistel networks keep half the round effectively unchanged. This
> means that half the round's output is a trivial linear function of
> that round's inputs.
But, of course, comparing ciphers by comparing what one round of each
does isn't meaningful, as what a round is depends on what each cipher
defines a round to be.
> Feistel networks are used with balanced s-boxes. Balanced s-boxes
> alone are sufficient to produce permutations. The Feistel network is
> another method of generating permutations. As such it is unnecessary -
> all you need are a collection of balanced s-boxes.
>
> Keeping half the round unchanged is wasteful in terms of getting maximum
> confision in hardware implementations.
That depends on the requirements, and on what alternatives there are
that also meet the requirements.
> One half of the round is being fed
> through s-boxes - this takes time. The other half of the round is just
> sitting around doing nothing while this happens. Instead it could
> usefully be subject to confusion. [This objection is only true if there's
> some sort of diffusion applied between rounds, which means that the
> outputs from the previous round are all needed before processing of the
> next section can start].
>
> If hardware speed is a significant factor, ISTM that use of a Feistel
> network is not going to give you the greatest bangs for your buck.
If hardware speed is a significant factor, a significant question is
whether each application of the whole cipher needs to be performed
quickly, or whether it's only the overall throughput that needs to be
fast.
If it's the latter, pipelining may be appropiate, and it becomes a
question of circuit size more than speed (you can have lots of very
short, quick segments). If it's the former, it's a matter of comparing
the whole cipher with alternatives (it's the quickest cipher you want,
which may well not be the cipher with the quickest round).
Simon
--
_______________________________________________________________________________
Personal: [EMAIL PROTECTED]
Yellow Skies: [EMAIL PROTECTED] http://www.yellowskies.com
Everyone does their own signature to be different. How does that work?
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: Q: Result of an old thread?
Date: Wed, 20 Dec 2000 00:26:13 GMT
Mok-Kong Shen wrote:
> Bryan Olson wrote:
> > Mok-Kong Shen wrote:
[...]
> > > I was not explicit and did not say that what you wrote seems
> > > not to be concrete enough. You wrote [If AS is n by n with
> > > rank m < n, then you can express AS as an n by m times an
> > > m by n]. So AS is to be expressed as CD where C is n*m and
> > > D is m*n. Which method given in the common textbooks of
> > > linear algebra are you referring to? Are C and D unique or
> > > could I take any candidates?
> >
> > A basis for the column space of AS looks like a good candidate
> > for the columns of C.
> >
> > > I need some concrete
> > > instructions from you, for I like very much to see if I
> > > could actaully carry out the computation of a tiny example,
> > > for that would obviate the need of any further discussions.
> >
> > How did your computation for the first solution come out?
> >
> > Merely carrying out the computation when given specific steps
> > will resolve only the narrowest of issues; my computer can do
> > as much. One who posts dozens of ideas for ciphers should not
> > be stumped by this linear toy.
>
> You misunderstood me. I have never done any real computation
> of an example. I am waiting to know from you a (concrete)
> systematic scheme of solving a tiny (specific) example.
You had no reason to wait. The first solution appeared step
by step and in posts that have the same date as the initial
question. You didn't even try.
> If
> that example could be solved without too much efforts (trials)
> then we can at least have some useful insight about the nature
> of the general problem, i.e. whether big examples could
> be similarly solved within reasonable time.
Call the size of each matrix n by n, then the time to solve
is order n^3 using the classical algorithms. That's typical
of linear systems. Note that breaking the system is about as
much work as using the system.
--Bryan
Sent via Deja.com
http://www.deja.com/
------------------------------
From: [EMAIL PROTECTED] (Gregory G Rose)
Subject: Re: SMS security over various networks?
Date: 19 Dec 2000 16:42:48 -0800
In article <[EMAIL PROTECTED]>,
Chris Kantarjiev <[EMAIL PROTECTED]> wrote:
>I can find references, for example, to A5 for GSM, and A5 having been
>broken, but no clear information about how A5 is or isn't used for SMS
>(as opposed to voice).
In the GSM system, all frames (whether voice or
signalling data or SMS) are encrypted equally
using one of the A5s as negotiated.
>I found one message in Deja that indicates that SMS messages over CDMA
>networks are "encrypted" with CAVE (which isn't very good, but does it
>really need to be, since spread spectrum messages are hard to intercept
>anyway?).
That isn't correct. Despite its name and acronym,
CAVE is a hash function used for key derivation.
Assuming privacy is turned on at all, CAVE
produces two privacy keys, called the VPM (Voice
Privacy Mask) and the SMEKey (Signalling Message
Encryption key, 64 bits). These are used
differently in CDMA and TDMA, but up to this point
everything is common.
TDMA:
The VPM is XORed into every voice frame, but not
IIRC into any other frames. SMS is encrypted using
an algorithm called CMEA, under the control of
SMEKey. See Schneier and Wagner's paper about
breaking CMEA.
CDMA:
Most of the VPM is ignored, but 40 bits of it is
used to define the PLCM (Private Long Code Mask)
which initialises the shift register used for the
signal spreading. This is not cryptographically
secure but as you point out does make it hard to
intercept the message in the first place. (It's an
interesting philosophical question which of LFSRs
or Many-time-pads are weaker.) All traffic,
whether voice or otherwise, uses the PLCM.
This is a hint that the PLCM is not considered to
be encryption by the spooks, since if it was,
super-encrypting would have been Right Out.
Signalling messages including SMS and DTMF tones
are encrypted using CMEA and SMEKey. CDMA's way of
using CMEA is arguably weaker than TDMA's, but
this is another question of primarily
philosophical interest.
Future:
Following the revelation of the weakness of CMEA,
a patchup algorithm called ECMEA was standardised,
but I don't know whether it is actually in use or
not. A further enhancement of ECMEA, called SCEMA,
is to be used in the next TDMA. AES (Rijndael)
looks to be standardised for CDMA. UMTS (the
evolution of GSM) will use KASUMI, an evolution of
Matsui's MISTY.
>Can anyone give me some pointers? Even for-pay reports would be welcome
>at this point.
The standards documents are now on the Web thanks
to the new export regulations.
Greg.
--
Greg Rose INTERNET: [EMAIL PROTECTED]
QUALCOMM Australia VOICE: +61-2-9181 4851 FAX: +61-2-9181 5470
Suite 410, Birkenhead Point http://people.qualcomm.com/ggr/
Drummoyne NSW 2047 B5 DF 66 95 89 68 1F C8 EF 29 FA 27 F2 2A 94 8F
------------------------------
From: Thierry Moreau <[EMAIL PROTECTED]>
Subject: Re: does CA need the proof of acceptance of key binding ?
Date: Tue, 19 Dec 2000 14:49:25 -0500
[EMAIL PROTECTED] wrote:
> when someone applies a digital certificate from a certificate authority
> (CA), does the CA need the proof of acceptance for the key binding from
> the applicant?
>
> Thanks!
>
Yes, it does "need" such a proof ... but there is no practical way of
providing it securely, so CAs do operate without a strong proof that the
certificate holder indeed agrees ... and they nonetheless claim to provide
state-of-the-art security (!)
- Thierry Moreau
------------------------------
From: Andre van Straaten <[EMAIL PROTECTED]>
Subject: Re: Steganography using text as carrier
Date: 19 Dec 2000 18:56:46 -0600
Chris Gillespie <[EMAIL PROTECTED]> wrote:
> Oh yeah, does anyone have any idea how the algorithm for the spam mail works?
> --
> --
> Chris Gillespie
> Researcher
> Dept of Computing
> University of Bradford
> email: [EMAIL PROTECTED]
No, but my guesses are:
- The order of sentences from a standard text are re-arranged. The resulting
text looks quite weird.
- Some words of the text are names or numbers. These are presumably generated
by the plaintext itself, or taken from an array out of a database.
For example, one sentence is:
"Why work for somebody else when you can become rich within 97 weeks ."
Another one (even a good one) is:
"Prof Ames who resides in Washington tried us and says "I've been poor and
I've been rich - rich is better" ."
And another one:
"Ms Anderson of Hawaii tried us and says "I was skeptical but it worked for
me"."
I'm not convinced of this kind of encrypted text. The sequence of sentences
is really weird and makes the whole thing suspicious.
I encrypted the text "I'm Santa Claus!" and had then a text out of 32 lines.
-- avs
Andre van Straaten
http://www.vanstraatensoft.com
The signs and the omens are everywhere
But too few see them - too few even care
(Lee Clayton - singer/songwriter, 1979)
====== Posted via Newsfeeds.Com, Uncensored Usenet News ======
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
======= Over 80,000 Newsgroups = 16 Different Servers! ======
------------------------------
** 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
******************************
