Cryptography-Digest Digest #209, Volume #11 Sun, 27 Feb 00 18:13:01 EST
Contents:
Re: CRC-16 Reverse Algorithm ? (Scott Nelson)
Re: On jamming interception networks (Steve K)
Re: On jamming interception networks (Mok-Kong Shen)
Export Rules (tboldt)
Re: Implementation of Crypto on DSP (Tim Tyler)
Re: CRC-16 Reverse Algorithm ? ([EMAIL PROTECTED])
Re: CRC-16 Reverse Algorithm ? (David A. Wagner)
Re: Snuffle source code? (Mok-Kong Shen)
The former CIA directors are just playing roles .. they are involved in the covert
action (John)
Re: The former CIA directors are just playing roles .. they are involved ("Markku
J. Saarelainen")
Re: On jamming interception networks ("Douglas A. Gwyn")
Re: On jamming interception networks (Guy Macon)
Re: CRC-16 Reverse Algorithm ? (Terry Ritter)
Re: CRC-16 Reverse Algorithm ? (Terry Ritter)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Scott Nelson)
Subject: Re: CRC-16 Reverse Algorithm ?
Reply-To: [EMAIL PROTECTED]
Date: Sun, 27 Feb 2000 19:28:06 GMT
On Fri, 25 Feb 2000 14:18:56 -0500, "Liu, Qingzhu [CAR:CF36:EXCH]"
<[EMAIL PROTECTED]> wrote:
>Hello,
>
>I try to implement an algorithm for crc-16 reverse
>(Poly: 1 + x + x^14 + x^16) in PIC17c756 assembly code.
>
>My questions are:
>1. What does the "Reverse' mean ?
There is no well defined meaning, however in this case I
think it's probably referring to the "direction" of the flow;
By one definition a "normal" CRC takes the XOR of
bits 1, 14, 16 and the input bit, and rotates the result
into the register, changing at most 1 bit.
A "reverse" CRC rotates the register, takes the bottom bit,
XOR's with the input and if the result is a 1, it XOR's
several of the bits.
The "reverse" CRC is more common, since it's so much
easier to implement in software.
The C code for a single bit looks like this:
if ((crc ^ input) & 1) == 1) {
crc = crc>>1;
} else {
crc = (crc>>1) ^ 0xa001;
}
and this is usually smaller in assembly.
>2. How is the dividing circuit looking like?
not sure what you mean.
>3. Is there a Byte-wise CRC calculation algorithm for it?
Yes. But for the PIC, you are probably better off
implementing it straight line. Wasting 512+ instructions
just for a few cycle improvement is unlikely to be worthwhile.
It only takes about 5 instructions to do 1 bit,
40 to do all 8, looking it up involves two computed
jumps, and a two subroutine calls, in addition to
the XOR and the instructions wasted in the lookup tables.
>4. What is good text book about this topic?
>
It's a CD, not a book, but I think the latest microchip example
library includes a CRC routine. Check their web site:
http://www.microchip.com
Hope that helps.
Scott Nelson <[EMAIL PROTECTED]>
------------------------------
From: [EMAIL PROTECTED] (Steve K)
Subject: Re: On jamming interception networks
Date: Sun, 27 Feb 2000 19:27:54 GMT
On Sun, 27 Feb 2000 19:00:27 GMT, [EMAIL PROTECTED] (JimD)
wrote:
>On Sun, 27 Feb 2000 06:12:19 GMT, [EMAIL PROTECTED] (Steve K) wrote:
>
>
>>Pretty good ideas. IMO "they" probably don't try to decrypt random
>>text, since that's practically always going to be an exercise in
>>futility.
>
>How will they tell 'random' text from enciphered text?
>(Apart from with considerable difficulty?)
Sorry, I wasn't any too clear...
By "random" I meant both random garbage and real encrypted text.
Unless there's a "-----begin PGP encrypted message-----" or some other
identifiable formatting code included, it shouldn't be possible to
tell the two apart...
:o)
Steve
---Continuing freedom of speech brought to you by---
http://www.eff.org/ http://www.epic.org/
http://www.cdt.org/
PGP key 0x5D016218
All others have been revoked.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: On jamming interception networks
Date: Sun, 27 Feb 2000 21:11:39 +0100
Mok-Kong Shen wrote:
>
> In a private communication it was correctly pointed out to me that
> my suggestion evidently entails too much work for the people to do
> and hence the idea is useless practically. It was suggested
> instead that everybody (it suffices, if there would be sufficient
> number of people who cooperate) appends to his/her mails or posts
> a few lines of random hex sequences. Since the agencies could not
> know whether these are innocent 'scarecrows' or are outputs of
> encryption algorithms, they would try to decrypt them. Since the
> sequences, however, are in fact random, they can never succeed,
> no matter how much efforts/resources are spent on them. On the
> other hand, they can also never be sure that what they have in
> hand are not secret messages, albeit encrypted with algorithms
> of very high strength.
After some further (private) discussions I came to the opinion that
it isn't necessary at all that there will be a substantial number
of people who regularly have the habit to append some random
hex strings to their e-mails. Suppose there could be one or a
few sites (run either by active information security groups like
the EFF for free or by some businessmen who provide the service
against certain small charges) which publish short messages of their
subscribers on their web pages similar to the announcements in
the newspapers. Then secret communications could be done through
sending encrypted messages to these sites to be read by the partners.
To be effective such sites should preferrably be in crypto-neutral,
i.e. non-Wassenaar, countries, or in the seven countries that have
been honoured with the distinguished mention in the proposed
final EAR. Of course, there should be among these petites annonces
a large proportion of nonsense messages (scarecrows) consisting
of random hex strings and only occassionally a few true secret
messages in order to achieve a high operating efficiency. Suppose
there are 0.1% of secret message there. Now consider the situation
the operators of the interception networks are in. Should they
attempt to decrypt the whole (or at least one half) of the bunch
of messages which are 'freely' offered to him? If yes, then
the probability of their task being (almost) non-terminating
is at least 99.9%. If not, they risk not obtaining some
spectacular plots of the gangsters/terrorists and/or (what is
presumably nowadays more important) contract bidding secrets of
foreign big firms such as those in the aero-space industry.
Since even 'small' citizens may sometimes have something that are
definetly not other people's 'business', I could imagine my pleasure
of submitting an encrypted message to such a publishing site and
drinking my coffee in a little internet cafe, while at the same
time my correspondent is decryping it in a similarly noble
instituion in Brazzaville and enjoying her favourite pizza.
(This practically prevents the identity of senders and recipients
from being tracked.)
M. K. Shen
------------------------------
Date: Sun, 27 Feb 2000 15:07:29 -0500
From: tboldt <[EMAIL PROTECTED]>
Subject: Export Rules
As I read the draft export rules posted in the Federal Register on
1-10-2000 the rules would go into effect in 120 days from posting which
wouold be 5-9-2000.
Is this true - or is that the end of the comment period and we have to
wait further after that????
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Implementation of Crypto on DSP
Reply-To: [EMAIL PROTECTED]
Date: Sun, 27 Feb 2000 20:01:57 GMT
Peter Gutmann <[EMAIL PROTECTED]> wrote:
: If you ignore heat and power requirements, the best crypto engine (in terms
: of bang per buck) which you can currently get is an AMD K6 [...]
That probably depends on what crypto you're doing.
If your task is amenable to parallel execution, an FPGA-based solution may
be able to beat a K6 of similar cost by orders of magnitude.
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
Might might be right, right?
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: CRC-16 Reverse Algorithm ?
Date: 27 Feb 2000 20:59:54 GMT
To quote Rich Webb in a recent reply on comp.arch.embedded:
*THE* reference site for programmers looking to understand and write CRC
algorithms is:
http://www.ross.net/crc/crcpaper.html
Look for the paper "A Painless Guide to CRC Error Detection Algorithms"
by Ross Williams. It explains how they work, gives operating parameters
for several standard CRCs, and includes working portable C source for a
model CRC implementation.
The model code is slow since it's not hard-wired for a particular
endian-ness or CRC flavor and is not table-driven, but this enables it
to be used with many different CRC divisors and reflection options. VERY
handy to be able to check the results of that tight assembly code
against a known good result.
The paper does include a table generation function and guidance on how
to implement a tight, fast table-driven CRC engine.
Keith
http://www.cix.co.uk/~klockstone
------------------------
'Unwise a grave for Arthur'
-- The Black Book of Carmarthen
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: CRC-16 Reverse Algorithm ?
Date: 27 Feb 2000 12:49:58 -0800
In article <eu7wttOg$GA.277@cpmsnbbsa03>, Marty <[EMAIL PROTECTED]> wrote:
> Second, when the state of a CRC is all ones it transforms to a non
> zero, non all ones state on the next clock.
Yes, 111..11 -> 111..10 (if the incoming data bit is zero;
assuming Fibonacci configuration, not Galois). Right?
> This state is independent (
> except for the lsb) of the incomming data bit.
Right. Now, if 111..11 -> 111..10 under input bit zero, then
111..11 -> 111..10 xor 1 = 111..11 under input bit one. No?
> Symmetry is not applicable here. 0's act quite differntly from 1's.
But if S is an initial state and M is a message, then
CRC(complement(S),complement(M)) = complement(CRC(S,M)),
unless you do something specifically to defeat this property
(e.g., appending/prepending fixed bits to M).
Therefore, if you have a problem with leading zeros in M when S = 000...0,
you will also have a problem with leading ones in M when S = 111...1.
Or so it would appear to me.
Where have I gone wrong? Perhaps there is some difference between
CRCs and LFSRs that I'm missing?
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Snuffle source code?
Date: Sun, 27 Feb 2000 22:47:13 +0100
helper wrote:
>
> There was an article Thursday
> (http://wired.com/news/politics/0,1283,34550,00.html) about Daniel Bernstein
> finally being given the go-ahead to post his source code for Snuffle to the
> net. Anyone gotten it, yet? If so, where? Thx.
I don't exclude that Prof. Bernstein has lost so much energy in
his almost hopeless combat against the bureaucrats that he needs
two months of vacation to recover before being able to update his
web page and render his code freely accessible to the world.
M. K. Shen
M. K. Shen
------------------------------
From: John <[EMAIL PROTECTED]>
Crossposted-To:
alt.politics.org.cia,soc.culture.russian,soc.culture.soviet,soc.culture.europe,soc.culture.nordic,soc.culture.italian,soc.culture.french,soc.culture.spain,alt.security
Subject: The former CIA directors are just playing roles .. they are involved in the
covert action
Date: Sun, 27 Feb 2000 21:43:20 +0000
In article <[EMAIL PROTECTED]>, Marc Jaworowicz
<[EMAIL PROTECTED]> writes
>You are such a good propagandist, why don't yuu leave Finland and move to
>Russia, or some other place where such crap is tolerated such as Iraq?
>
Marc, don't bother wasting time and bandwidth on a troll.
"Markku" is just another alias. As a Finn, he/she should have no
trouble translating:
"Vientipalvelumme hoitaa ostostesi lahetyksen
ulkomaile. Ostotesi lopposummasta vahennamme
liikevaihtoveron 14%, elintarvikkeistais 5% ja lisaamme
toimituskulut. Ulkomaille matkustavat asiakaamme
saavat samat edut, kuin toimitamme heidan ostoksensa
lentokentalle, rautatienasemalle tai laivaan."
...... or at least telling us the purpose of the building opposite the
main bus station in Helsinki.
Other nationalities claimed have been English and Canadian, and recently
an attempt was made at North American.
Over the last 10-15 years or so, "Markku" has spammed the networks with
the similar paranoid "they are spying on me" stories as the content is
identical and the writing styles of the differing persona appear to be
the same.
Don't waste your time.
--
John
------------------------------
From: "Markku J. Saarelainen" <[EMAIL PROTECTED]>
Crossposted-To:
alt.politics.org.cia,soc.culture.russian,soc.culture.soviet,soc.culture.europe,soc.culture.nordic,soc.culture.italian,soc.culture.french,soc.culture.spain,alt.security
Subject: Re: The former CIA directors are just playing roles .. they are involved
Date: Sun, 27 Feb 2000 21:54:39 GMT
Actually, I am just me, Markku J. Saarelainen. I have not been doing whatever
you are saying. So just read my messages. They are based on my records, notes
and other proof. Actually, I had some difficulties reading your Finnish
message...
Best regards,
Markku
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: On jamming interception networks
Date: Sun, 27 Feb 2000 22:21:30 GMT
Mok-Kong Shen wrote:
> > > In a private communication it was correctly pointed out to me that
> > > my suggestion [encryption] evidently entails too much work for the
> > > people to do ...
> > Not if it is done automatically, ...
> > The main problem is getting interoperable encryption to occur *by
> > default* ...
> I don't yet understand you. One could simply use a PRNG to generate
> the needed hexs and append these just as one appends one's signature.
I thought your original suggestion (to which I was responding above)
had been for everyone to use secure encryption.
> ... the hex strings of 'unknown' nature would actually cause their
> resource-consuming analysis mechinery to 'run'.
As I said, you have a badly flawed model of how interception works.
Untargeted communications are not analyzed jsut because they might
be encrypted.
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: On jamming interception networks
Date: 27 Feb 2000 17:34:27 EST
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Mok-Kong Shen)
wrote:
>
>Since even 'small' citizens may sometimes have something that are
>definetly not other people's 'business', I could imagine my pleasure
>of submitting an encrypted message to such a publishing site and
>drinking my coffee in a little internet cafe, while at the same
>time my correspondent is decryping it in a similarly noble
>instituion in Brazzaville and enjoying her favourite pizza.
>(This practically prevents the identity of senders and recipients
>from being tracked.)
>
Go one step further: keep the passphrase and the encrypt/decrypt
program in your head, write a new copy as needed, never save the
decrypted text to disk, and delete the encrypt/decrypt program
after use. See [ http://www.ciphersaber.gurus.com ]. I took
the extra step of obtaining an old 8088 laptop (better against
TEMPEST attacks) that runs DOS 6.22 and QBasic to do my editing
and encrypting on. Thus even if you take over my networked
computer you still don't have my plaintext.
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: CRC-16 Reverse Algorithm ?
Date: Sun, 27 Feb 2000 22:56:30 GMT
What a mess!
On Sat, 26 Feb 2000 22:23:34 -0800, in <eu7wttOg$GA.277@cpmsnbbsa03>,
in sci.crypt "Marty" <[EMAIL PROTECTED]> wrote:
>David A. Wagner <[EMAIL PROTECTED]> wrote in message
>news:89a959$to6$[EMAIL PROTECTED]...
>> In article <#txNt0Ng$GA.262@cpmsnbbsa03>, Marty <[EMAIL PROTECTED]> wrote:
>> > Inserted and/or deleted ones at the start of a ones initialized CRC are
>> > indeed detected.
>>
>> Did you mean "not detected"? I thought Doug Stell got it right.
>
>No, I believe Doug's incorrect.
Doug is wrong. CRC *does* indeed detect every 1-bit at the start of a
message. Missing 1's *ARE* detected. Extra 1's *ARE* detected.
Missing and extra 0's are also detected.
>> Surely I'm missing something. We know that, when the CRC uses an
>> primitive polynomial, the all-ones state 111..1 goes to 11..10
>> after clocking it once [*]. In other words, if initialize the CRC
>
>First, CRC's do not ussually use a primitive polynomial.
Generally false. Modern CRC's normally are primitive. CRC32 is
primitive. CRC-16 and CRC-CCITT are composite with a factor of 11,
which is the same as parity error detection. Systems which previously
used parity were thus in no way disadvantaged by using CRC.
>They serve
>a somewhat different purpose, error detection rather than max
>cyclical length.
>
>Second, when the state of a CRC is all ones it transforms to a non
>zero, non all ones state on the next clock. This state is independent (
>except for the lsb) of the incomming data bit. The data bit
>is not xored in before the decision to toggle the other crc state bits.
True, but confusing. Assuming a shift-left CRC, what happens is that
new zero bits are shifted in from the right, and if the data bits are
the same as the shifted out bit (they will be with all-1's CRC and
data), then the poly is not added in. So if we have all-1's, we just
accumulate 0's until the CRC becomes zero, after which data 1's imply
that the poly will be added in.
for shift left:
if (msb(crc) = databit)
crc = crc << 1;
else
crc = (crc << 1) ^ poly;
>> to all-ones and feed in a zero bit, we get the new state 11..10.
Correct, assuming a left-shift computation.
(I think this is from Doug.)
>> But now we can imagine initializing it to the all-ones state and
>> feeding in a one bit; this complements the feedback tap, and so
>> where a zero was previously fed in, now a one will be fed in, and
>> thus the new state will be 11..11, always.
False. Assuming a shift-left CRC starting at "all 1's," we get a new
zero with every shift and every data bit. Since msb(crc) = databit,
what we don't get is the poly addition, and that is the way the
rightmost bit gets set, so it stays zero.
>> Consequently, if the CRC is initialized to the all-ones state, we
>> can insert as many one bits at the start of the message as we like,
>> and it won't affect the final result.
FALSE. Try it.
>Another way to see this is to note that the high speed lookup table
>entry for 0xff is not 0xffffff.....00 which would be the case if the state
>register remained all ones after recieving a 0xff byte.
Correct. CRC32 with crc = 0xffffffff and data = 0xff produces
crc = 0xffffff00
>> (It may be easier to see this by symmetry: a corresponding property
>> holds for the all-zeros state and prepending zero bits; and everything
>> is linear, so you can just complement everything in sight and by
>> symmetry the property will still hold.)
>>
>
>Symmetry is not applicable here. 0's act quite differntly from 1's.
Well, if we have "all-0's" and data of 0's we will accumulate more
zeros, which will not detect leading zeros. The whole point of
setting the CRC register to all-1's prior to CRC operations is to
detect missing bits. I suppose the symmetry breaks because the
computation is crc = crc*2 instead of crc = crc*2 + 1.
>> Where did I go wrong? What am I missing? I'm confused.
>I hope this explanation makes sense. Try out a CRC-32 which starts
>with all ones. You will see it changes state when fed ones.
Exactly the right answer: Try it.
>> [*] Proof: Obvious. Treat it as a free-running LFSR. There are only
>> two states it can go to, i.e., 11..11 and 11..10. If it goes to
>> the former, then we have a cycle of length, so the LFSR isn't
>> full-period, and thus the polynomial can't be primitive,
>contradiction.
>> When you eliminate the impossible, whatever remains must be true,
>> and so surely 111..1 -> 11..10.
Alas, CRC32 is primitive. Now, about that proof....
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: CRC-16 Reverse Algorithm ?
Date: Sun, 27 Feb 2000 23:05:34 GMT
On 27 Feb 2000 12:49:58 -0800, in
<89c2lm$un2$[EMAIL PROTECTED]>, in sci.crypt
[EMAIL PROTECTED] (David A. Wagner) wrote:
>In article <eu7wttOg$GA.277@cpmsnbbsa03>, Marty <[EMAIL PROTECTED]> wrote:
>> Second, when the state of a CRC is all ones it transforms to a non
>> zero, non all ones state on the next clock.
>
>Yes, 111..11 -> 111..10 (if the incoming data bit is zero;
>assuming Fibonacci configuration, not Galois). Right?
Right.
>> This state is independent (
>> except for the lsb) of the incomming data bit.
>
>Right. Now, if 111..11 -> 111..10 under input bit zero, then
>111..11 -> 111..10 xor 1 = 111..11 under input bit one. No?
No.
In a shift-left CRC, 0's always shift in, and this is independent of
the data value. the only way the rightmost bit gets set to a 1 is
from the poly add.
>> Symmetry is not applicable here. 0's act quite differntly from 1's.
>
>But if S is an initial state and M is a message, then
> CRC(complement(S),complement(M)) = complement(CRC(S,M)),
>unless you do something specifically to defeat this property
>(e.g., appending/prepending fixed bits to M).
No.
>Therefore, if you have a problem with leading zeros in M when S = 000...0,
>you will also have a problem with leading ones in M when S = 111...1.
>Or so it would appear to me.
>
>Where have I gone wrong? Perhaps there is some difference between
>CRCs and LFSRs that I'm missing?
There is no real difference. Certainly a CRC has a data input that
LFSR's do not have. I suppose what you are missing is a understanding
of the CRC algorithm.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
** 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
******************************
