Re: Minimal crypto OTP by dummie

From: machine99 (please_at_no.spam)
Date: 04/20/04 

Date: Tue, 20 Apr 2004 19:06:36 +0200

> > Using random numbers without some sort of pre-processing, wouldn't that
be
> > risky? Wouldn't it be necessary to generate a new random sequence if the
> > first one somehow reveals fragments of the message?
> ...
> > If the 'enemy' already has some info, they can compare the existing info
to
> > the fragment and see if it makes 'sense'. If it does, they have yet
another
> > piece of info they can use to trace the sender and perhaps catch him.
>
> I hope my explanation could be useful: xoring a message M with a
> private random key K of same lenght L, element by element, resut in a
> cypertext C where each element can be decyphered in any of the
> possible states S of the elements with the same probability (each bit
> can be decyphered with equal probabilities in 0 or 1, each byte can be
> decyphered with equal probability in any of the 256 possible byte's
> values).
> So M can be decyphered with the same probability in any message of
> lenght L, S^L possible results. This is equal to state that, without
> knowing K, M is unrelated with C and vice versa, so C is not
> decypherable unless brute force attack trying S^L results (possibly
> S^(L-n) where n are known bytes of M). However this brute force attack
> will be equal to create the M form nothing (or from the known bytes)
> and obviously noone can prevent a monkey to hit a billion times a
> keyboard and write Window's source code ;)
> This is why randomness of K is improtant, another good reason is that
> knowing C and some bytes of M is equal to know the related bytes of K,
> since xor is an easily inverible function, so it's important that K is
> really random or the knowledge of some K bytes could be used to cast
> other K values and compromise the cryptogram.
> Why shouldn't be obvious K sequences be discharged?
> If you prevent the creation of those sequences or if you simply
> discard those results and make your RNG create other sequences unless
> they are good, all the previous schema is compromised since possible
> output of encryption are less than S^L.
> Why? Because you have two ways to check if the sequence in K is "not
> good".
> Firstly you can control if the value in K[i] reveal M[i] (in example
> K[i] is 0), but in this way you have (S-x)^L possible output state and
> this estabilish a relation between M and C and this knowledge can be
> in some ways used by the attacker (i.e. I know "e" in M will never be
> "e" in C, that's less shure to not knowing non relations between C and
> M). So the security in non correlation between M and C is lost.
> Second if you check if sequences in K are trivial (i.e. 1234567, or
> 111 or 000...) you estabilish a relationship between elements of K;
> i.e. very simply K[i] must be <> K[i-1], or K[i]-K[i-1] must be
> different from K[i-1]-K[i-2], resulting in (S^L)-x possible outputs, x
> related to the checking algorithm used.
> So knowing some M elements you can know related K elements and try to
> cast other elements of K, loosing the second good feature of OTP, the
> non correlation between key's elments.
> Those two kind of correlation can be not easy to use to attack the
> cryptogram, but obviously are weakenings compared to a totally
> unrelated system.
> So "bad" K does'n weaken the OTP, not only they are practically very
> improbable, but most important the message will always be teorically
> unrelated with the key so "saddam is here!!!!" can be "Saddam is not
> here" with the same probability and the point is that since the
> probability of a revealing sequence in K is the same of casually
> create the same M sequence from nothing no C sequence can be
> ***anyway*** proved to result from a trivial K sequence, so simply bad
> sequences doesn't exist.
> The only check to perform is that the RNG device is working properly,
> in this case IMHO is better to analize operational parameters of the
> device, not the apparent quality of the output.

I'll probably have to read this a couple of times before I understand it but
thanks for your feedback anyway ;)

Relevant Pages

  • Re: Rational numbers, irrational numbers: each dense in real numbers
    ... that it is extremely unlikely to have the sequence ... Such a probability distribution, ... probabilities of all but a finite or countably-infinite ... Any uniform nested-finite-distribution system which is ...
    (sci.math)
  • Re: Howard theory - "cannot be computed"
    ... in fact require some sort of probability calculation. ... the expectation of chance alone. ... but some of the differences may arise rapidly by selection for changes ... that the current sequence retains or changed. ...
    (talk.origins)
  • Re: Linfords Fallacy
    ... it is not true that the probability of having all ... heads is the same as the probability as having any mixture of heads and ... or tails than there are series of coin flips with only heads. ... It is true that the probabiliy of any sequence is the same ...
    (sci.math)
  • Re: Rational numbers, irrational numbers: each dense in real numbers
    ... that it is extremely unlikely to have the sequence ... even in principle to determine whether an infinite sequence of coin ... the computable reals. ... Such a probability distribution, ...
    (sci.math)
  • Re: Minimal crypto OTP by dummie
    ... Wouldn't it be necessary to generate a new random sequence if the ... >> first one somehow reveals fragments of the message? ... > possible states S of the elements with the same probability (each bit ... So the security in non correlation between M and C is lost. ...
    (sci.crypt)