Re: Minimal crypto OTP by dummie

From: Giorgio (giorgio_at_bignami.zzn.com)
Date: 04/20/04

  • Next message: ererz: "Re: COMPUSEC" 
    Date: 20 Apr 2004 02:42:59 -0700

    > 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.

  • Next message: ererz: "Re: COMPUSEC"

    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: 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: The last ancestor of all life
      ... what is the probability of flipping a quarter and landing ... What is the probability of flipping a quarter having heads on the ... Any specific sequence of heads and tails will have the same odds. ...
      (talk.origins)
    • Re: Probability of arrival n happens at time t in Poisson
      ... The birth process generates a sequence of integer numbers following a ... Knowing that in time T the process generated N numbers, ... probability that number n<=N was generated precisely at time t (where t ...
      (sci.stat.math)