3
$\begingroup$

The Unicity Distance for the DES cipher is around $8.6$ characters, and can be calculated using the $U=H(k)/D$ formula, where $D = R - r$, and where $R = 8$ is the number of bits in a byte (ASCII is 7 but we are rounding up), $r \approx 1.5$ bits is the average entropy of a single letter in written English, and $H(k) = 56$ bits is the DES key length.

If the above is correct then, for a 16 bit cipher, your UD would be around 2.46. Surely you need more than 2 characters to tell whether what you are getting is valid English. Can anyone explain?

This is a follow up question from here: https://crypto.stackexchange.com/a/22929 The code to run the experiment can be found here: https://github.com/coolfeature/sac


Here are some calculations:

Unicity Distance is The Entropy of the key space / the redundancy D = R - r Assuming R is 8.0 bits (ASCII) and r is 1.5. H(K) / D == 16 / 6.5 == 2.461538

We need 2.461538 letters to get a meaningful message.

65536 candidate keys - block size 1 (2 chars) possible meaningful : 8 - chance of getting a meaningful msg: 0.000122

2809 candidate keys - block size 2 (4 chars) possible meaningful : 64 - chance of getting a meaningful msg: 0.000000

1600 candidate keys - block size 3 (6 chars) possible meaningful : 512 - chance of getting a meaningful msg: 0.000000

896 candidate keys - block size 4 (8 chars) possible meaningful : 4096 - chance of getting a meaningful msg: 0.000000

20 candidate keys - block size 5 (10 chars) possible meaningful : 32768 - chance of getting a meaningful msg: 0.000000

20 candidate keys - block size 6 (12 chars) possible meaningful : 262144 - chance of getting a meaningful msg: 0.000000

1 candidate keys - block size 7 (14 chars) possible meaningful : 2097152 - chance of getting a meaningful msg: 0.000000

The key 0x431a(17178) found after 7 attempts 7 blocks (14 characters/bytes needed) - DECRYPTING... Message Entropy = 3.854248670673993

$\endgroup$
7
$\begingroup$

A 16-bit cipher has $2^{16} = 65{,}536$ possible keys. Thus, if you try to decrypt your ciphertext with every possible key, that's how many different (and essentially random) plaintexts you'll get.

Your calculation suggests that $\lceil2.46\rceil = 3$ bytes of ciphertext should be enough to uniquely identify the correct key, assuming that the plaintext ordinary is English text. Such a short ciphertext would normally be characteristic of a stream cipher (or a block cipher in a streaming mode like CTR or OFB), in which case we can assume that each ciphertext decrypts to 3 bytes of plaintext (which, for an incorrect key, will be effectively random).

So let's test it.

I just wrote a simple program to generate 65,536 random 3-byte strings. Out of those strings, all but 3,399 contained bytes outside the printable ASCII range, so I filtered those out. Here are all the remaining ones:

F\G %EZ Cv> N}Q W&l LS} mM` "'8 Zi+ {KB '`j a6@ ;7O 3Hc }fH }&d W@L )]v 9Qy r1Y
ZG2 dc} `'x @4? WiC #7J T3' dq: s&. is_ laK Xr! fPi "MD LS4 (oz ELS 5${ ?6" E@,
PJ= S;C u|G :ap 1V~ ?Or g2V uE4 (O7 O3J bQ# a:0 k\: ~"" rWf eW4 Iqg bdT Oe) DYU
]n% A\V LzT s/N 1JO lZF *SQ p}/ YNY -V9 3f< r?g *Kp yyp E~Q <Jk r'w <^K c+_ w*w
iRt 8z, Fyf nq` K+. DuZ O<D 3co -Hz t?" !$S s`! ;wT }-M ZJI C9Z v8a *,D QcX 'cq
iM) $YX IDy K}9 Zmm J!y z[@ dXl $TC bR5 YDF 9/G $-p Pzu  Ff wpI {d" ~%# 'xw hpg
'[h E\7 Qsp ur# YN" TZm -}0 W(` T$r ~.J tKK ?~m \Y8 30] *P^ YlH g R # 4 nhs $ts
HS5 _i5 /2= al- w.t T+, ECg bU: Z}V w?6 #z  `R) ]n{ AiH jw> ;f1 (#Q  `S H_; a_O
n){ [Mt &"D xn  cr6 hJ~ HA2 ,gb ^/H 2M! &cZ }9K +wg Ivn {b{ ci= O7L %N, pac )|+
)n[ ivn td2 ^S} $Rf }[p %n% yWg F+V y-h F.6 36w D(A M-h Bea (yt Ka| w?b n)L z7W
8:d .l\ `|E f*" 8N% :_N $:p Z w K"l &hV Pr_ n/u $d- g   3L] g%y C|% S>P O[{ #IV
g"6 >tA Jp| Q={ jaM Q7U !#X pv" <JL t6= JIl %,` .K\ M,6 "MV kPH rMH ^T* .Hd jST
yX[ (~p GX} pSx S}?  @A }f_ Hy, ja1 cnp '5- zuy (\] u6w 2R% v([ QBK /jR ewr X)i
Z[: .F{ $]( {IS V4J ?01 K@+ 2VW |Ci -M* eb. oA8 1," h^s 2Dx V>F ndh 5VA `]  u(l
6R. -G~ s,b !Rd O]E [%o xBg wfd ;`^ L0' )<j y)M VO= /I* unB 3Ib VDi ~ok WBm BL-
u[9 1P6 @#d G=w %V/ YA> 'CT P}@ *E` *4H :$z /o$ w_J iBC lG| x}^ m7^ ]4v vz\ }-@
TE- XV{ ,6# p7G IvG tID 2g! >N^ x^" :^[ EG. 6a1 "D$ {YG QNS w}o +.f ~F- "kc i){
bq0 .I_ \gX 5wH .RQ 46U ]:+ sGx xOX 2<D ozM `|< k+: }$I ].B m%: Z1! K&^ k]] 4l2
`aW .q? 'K& zwp kcA O]p l@B (fg kJd v ^ k*> q:} q1f `_$ iz. ?b( O\H ~Cp )~' BMW
rnx \ms ]cy X!G Fs' zg1 px` 'v4 'V= jn1 ,"_ E+` ==, 2^T s77 <Ji "py uni 0~v 5lo
(Nd BL< ]V0 u"' r[= 6T\ oQW [pR cIN ~w5 |uT .&H QO8 itz g'E "Ea q}G h8" xH8 .%\
g^F Hh: #$b vg$ }+* #hz }TH v!T .~> 2=f QFs c;M 7SM "i| .3V VH4 {5Y ^b_ {q% w%/
QJ+ !u: m>> 7&g _`U Dwh 'OI :uC a!- !go f;1 3 m QqV !&. Xg> Dg` 71p UnJ 0Vc TLO
F\2 %(P w/G aJC SO8 ,k[ h#e 4r0 YG} PD2 |f^ #Q* ',L L-2 W"# ',n ukt ]`! qp! p6R
*`; il  Z!L uG+ S"" bJ$ kpX jRM kWM c4% z{8 0]! ^UK s^M ,$1 .TX +r! .D? U<+ Yr$
-i` 8-- .sg d&: zIZ sD| cVy :`U I"& n]u t;8 h4c lX} E P :9d J # LQX AdG VLP f8^
2rj hsg Slu o=G G"^ CEu %9) 'l4 i6P L$~ \jo hNl {l8 /RO 53V W}w .:O #Ov M'* 6yx
olv j[: XmZ Uus OUK hQN <mZ 0(& 6T5 _<e `w> $Ym F+> )!& j~8 _I* <t# VL~ L:M -t 
:`r r9^ A<F 'L; z1g nzG :&= wp) KNk Z5f i)D @pC z-] m=  -j4 mN? qC) l5[ 31w ^,Q
1FZ w<T r!N R?} PaC edN Owa '^> }>; zju !XE ,h4 Ugx [=Y _vx "qf czs zM, M$e OW]
0o. X]` zT` /Fb k~} TVb z2B 0?c W{< *?g mpg llL .)8 ;1S '8j UO| ~a_ soU z+Q Q,e
L # ]Jn !jZ .,# M6{ Qyj m(| vPF  MY Z-5 :]^ Pt2 k[+ mYO W&D `"; <bF ]ZQ L?9 (-}
aE: yz1 9b) .pK t5= sDq eVx ?kL n*/ =B< (gl gv" lB/ ]o8 RQ6 r~_ DWN tY> q2Q 3-U
QeZ .Xx "]f B]3 xjS ]V9 E+c (Kp X.: wiD J9A m'Y _4j |}L SPL 3k, G4I zHn 3u6 `I'
Ka# D5. eaI 1p| t.Y ]"E zA; 81w Qzg !hK W@" FI( T7[ d9' Hp; BXa u@d &=[ b'8 'B&
:aF m.C zjs A)| Oxt ,so 37H 6VM P|/ /|U 9Q, lnn s%' |l0 {Xs q|F q ( 0)v p`z ):S
dZ. @;t ]Jn JVc .CD !+& #Vg %6Z VOl QoK ;z3 9A: m_X ",4 TQ  #}L  }J :O[ GPg $y<
|k: &f) (Ak Mx, N\L "bC 3}A +rL :<= .(I L?x D&] {Hr Np1 n*} 3n{ B<B Ub> edE F5@
I@_ Tv[ 4#9 j)J Na9 F}b 9T/ H#b .<Q WGC yQ+ ,oJ [Q% (rh 6C9 zw~ 9PS 0EG n$f o# 
:.l 1!l 9}J b<2 fh% ^nb x<_ h9< DRO ed/ V>Y FlN 5zL 'H_ ssN pNL k'E |hR A~a ?98
s7G _4v a42 !zc zmg Bp| (A^ 6*_ rAv SES 'x= T*R <PY anf |pd #{g J%* ,2) <}? *1G
wi< T)q yq# +_z B'> s.> f|R GOY $Zo xEi M!a tHB 1Q  16* |im ./! 3W< zKl k+' q?o
&h- ^[" wu. O3I sU] 1.Q k+/ I*h -<; "V/ +R8 5&c ,>e 9p0 4zU NUG 2{b ity qz^ Y@0
q%] Kmj <@! $Cm wn| ?m] Ug} 'TE +{' Esj L<Y 7;t d39 ^Z3 R6J DCl ORt ME\ 3JU [Jh
TqK Ys  0{/ `ZN zOL fd% $'y |wp CJ] Y:L kp8 XV4 t+x n(g U`$ AcT eCJ fQX `3p n9R
[k; .;A c(c khd >P7 A~2 6xr ->_ $:Y |g% iwv ZC@ -'" Q"_ ("+ nGT 4px rAQ p,. \tb
Fyv QzQ >u? ]NM 'o@ 9N$ :lQ GwW OSN u_> Ixi ~Fs qB) 2C+ +IJ [X- ,)t  "Z <cV ',T
K>e Gl6 R[< y_" ?Q\ ;jL F`H ?mb `j7 f!M ~#Z BA7 ENP e'+ `Jx ]** HA> sJb Dh, na/
(~A K0Y 8>m X?t b'j }0I R!P og. c{V  if _Q( D/E Ph> v0  8Ui P/@ )3/ yhT lrk >*F
j]  vaL wRz xK& 0yk =+f |W! Q]L R7U Zqz 6iT  ?- " 7 v#8 /\~ gR` `+h C:, `;T jIo
IpB 0oz YH@ f&: ou^ Rp} k8@ rJZ yw- i|{ Jr{ %Ak 1,\ OLh P[n e&@ !.P GRY y?d /me
)od -xU f4= (X= :0S [Kj 5,V w`S KCA v2j VOC D#g &3t 'r7 bcW V'd p!r %E7 KG` e\5
c_Q vJ  Lym up" 2e% aC} :Sp "PO  br i1% jno W+G !~! [-2 {N$ M)r GPl 7|r :R^ 5f*
1i= Dew {?b )>g |8{ tA@ /Or _#Q #0Q %%G HN? |W[ *)] %fr InF QPJ k:> ]At y<. n>v
~6L ]z< qPt KJM tx> ;)} 5cF J\w 0z> y!M ahV (Js ^ow V[5 LuV {"4 o?) >[$ C@  Ri|
b{N r4s U92 E)s {!7 h)7 1t( Hp! /iM W$2 q"s tFx ?)5 '6u t_; f*D 2=~ &5k Ok7 9MY
cWO SHs dC> >6( @L- F57 t:& v0y X=j PG{ ?#[ {Lz aEO }~I \t! Z<+ lAy mHf 2AP ~:_
eb# [ko mO? 2|U ND1 8Wv @'0 |B$ OX} 6)q `z. H{& 7Y7 o2Q Vu. 2M# [NB &(W 39[ fb$
9u? L<w _G  l-Z 1Pt rGt Hnq ^y^ + $ 1R% q\W 8{Y aq5 4\] W\O 3Yc `c% x.P MV. +B/
y&0 @bZ Zu6 4d( \tX gUq #/] b30 XI[ |?3 #>2 qQC 'x4 (>' x.W %A< i/3  kd '~z |Dm
pc' S|P O[' u07 */1 zO{ />c %(N 7<X 8r8 <6e #(R GyR %}V l(6 /PA #/6 U#8 N+\ 6tS
sJ| {[e VK_ @[p bmV %[, q,% m4U IHQ 0O> *88 h36 !1, C"I zWU b-d -SL ?m! Uym CbI
8dm (|b [I, 6M5 3{L -T2 =?S =p8 /9; _)b  WC 9uQ 7h( zU% E*J #{0  e" OH1 BWf zQD
9}L I1? UTT hvU ,uB Y22 r;% K.j "}u 2Lt @)2 OOX !3e "E| *c8 )!9 6l* ,Cw -Lb h5V
/60 :!  5YP J*/ a/} {.7 2*4 po5 Ea$ hGd 8nH u"| Ls+ |*Z -he A_y /b* 2%> ]lv MC_
Cf| E8{ w,0 3@v kXp jrj !{! 3@E Buk 6&2 )J5 +~f fBO 4SD _F| yU" @uW V[Q T1@ ]Ax
YMg tcQ +|c nHG S!z (g> _*K W;M .AN }w$ hIQ @EG SeO fH; yZa uGx 5;^ >F_ eET `(?
!lH ;Gn ^Fn BWC MZf #!h vjj p'o /`i J*; #.F l`t |wf :U@ MO6 G`O j1/ \v+ ;!{ H]{
g'2 kc0 Y]u =aL g<0 (4z zMl !ov ]v: [p6 mr| 9TT g\= XVZ Hiz TAl +*f X2N kuS ^%M
^/M *|0 188 "cU eBH 6!| [|( *9g 0bu .M* o][ %m` ~9e exz   s sX6 JX" 8\R )}P /^K
U(` fwV 8wJ 45H 9QM /K) z%V j4v (^9 zRx j9y cI% mf^ JEa 1,[ J00 \_{ iSF Rj3 zn*
0C  0r: p k _]j 9<A =Xx \UD ^PR ^bV }YZ hXJ "S% Urk _y8 kwh GJ6 pr< gws [7" qvJ
pRB 1/| -U# $1^ uSJ l<; +mQ HJ| aMG TF\ `"' :Kt dR{ 3Zc LiU [CY bP1 GPX %|_ 0bH
l6? &+b dQ2 gFO Iw< RY% iVp A>g Fm( ;,J JEQ @<* p64 P}( +h_ V(4 +/? 7cQ GQ. 8{_
\s3 ?z9 ~aP B-2 <vg  lk h~v `:T #>m 9Sy iyc M8/ \Te g>\ ;.1 &c7 W_V VCZ x[0 66g
g3= cI{ R_, m3s &x$ Am' ==3 r)c NHG |)H !~O C4) L.> 7Kv bO< R!> DZ0 62o 'tO  ?%
g4o T_t @Zj tBi [,t u:V N}* qDX Wz< ;e> d$* X|F m?/ Xp( %0] uP5 (u2 qi! y`\ B[\
-{6 H]C 9:| (P5 EUu u)a (%+ N<B 5jF rL& 00e -'c I g !3  FCg I[R `%\ aGI 8Vy {oD
nTX F@t $RV ge5 E6e L!% V~  Qno =f' 5$m kgk  l7 %CB Z3T 2v` 5[" x`l 5@- dmx oXT
six EXh TK^ dz@ %mw zo] *@U 91F ?c) Oni OZ{ drv *EC 9l\ "=? 5;* kB3 ?&z W0'  G\
q%j Cr_ ysl ?_O bp: IXv A3) <Y% M w 0&Q &oT Gdp Hj{ lvd *h6 w,W z~X kZ& B]Q %/"
;IS t$[ m0* UHL ~U4 uA& anv w_[ ijW qcV >z| U;$ JY\ #:. }N~ Rm+ Z2~ L:y vCg 1)i
AH{ YG8 s'+ c}# P!W `e` Wr+ ^1K r!6 ao{ Q%P j<# }Q= {+- _8] \U` D@o I`+ i)R JJv
6?V z?? fx# Z+z smc H!y ]4< :J| u2T _dK lvU }I3 &j@ ;;4 c|A D87 ,y] K[@ |.f ,?I
VS0 .dk q4' "RW vZg gvP o*b \#. uX~ ~#: BUY X%S Kuv <"? kMP gWR @X` tNZ 1l~ "tc
ZMb @*+ )/u ;eI L|y ;RS XFR VP' Z}s ?y9 F$  kEK &Hn qoA a`d ht? \.w [w4 Bv[ w)w
oc  }fl lo$ vUk p3R `(h ")i `LB 3z$ go% Wvz A;9 !!Q L#G  Pj  CC 58c qhI |FL &L1
CmL -#t M@p gkb H?P b6: i`- XSC @:5 e]m )4Z u#b <}Z 7NB >i? {@Z k"f Qm2 $YM k9a
`z5 .%4 $6$  JT NPC D<; swH tkf j>) ;}e &jF l{o k&+ h&K ,RN ]I" 4vT CUR 'gb dV/
fFH ('v k_Y LfA 2y; RDV j)B Ces kX" #]T |S= 6`8 h'a @w^ TG$ [g$ 4#6 'r7 KQX Z6b
3$I MXQ /l  ph& -F6  0] :k. j?' US3 =S} |v3 (A1 iv> 2a= x%h a)K C@8 4H^ `Wq (2z
)30 y9- Cur [>/ [V/ -}Q `Bh Nti pHx ?d? */1 j0> ]i2 +9W yw" Glq w6Q ?R' &db E2`
]F. $sc 0?w }/& }:P =~M 1Dz |rg ]uk l`U UIg V73 a~% 3fd kul |P$ (#d j>~ mwS jJv
kfS %?| e`Z (B3 f[t =e} fg^ 0^) ju{ P'X cgW lJk Bb4 v%\  #/ D$c uJQ yb4 Q V TLq
^"G fK| bY) br7 (.^ 7Ep 380 Y9n u<  dFv ~pm J;. Te[ g#3 +k| 'Dx oPS Wu/ %@F 1k?
eGo Aw" -m/ 0)A t39 l&M ^*^ En" N`2 ~tG q[v nN/ %3!  H0 +w@ c\a m4T E,- \+* *0.
VA] Ma% "cc 9W# m{f 1Vg ^I$ w 0 nyY ]h= Wc9 (9l ./0 "69 =8z !?$ qB+ $>j |1g EUo
x!5 j8G 7IL d4% l`M gk= vh: F4o W)E >o! qaB x/n l79 RLV YVC +|c D"$ 95j ZCH dD2
foC }T& #di ]~j OP} bCs n'J D/t <!\ \#" hP0 n51 (Xz 5es K&o RM1 !41 ~U[ nw5 &h'
>Z| +Lo 0f| Fe~ jF^ kuu A~B ZVx `$' V0P J@2 L1C dn% w@b ^Tj KM< uyc Q7d XLc 6K%
c~" %Z5 R,5 /~= nm: fN6 %Zs 5u+ xQC M`W (@- a$[ Ns; |_B 911 Kqg %PZ 8}* |>+ \]6
%gc ~*i ATZ E[x !M3 >ia wZ! War >t2 HDE ~Pd ]@j 11C |!0 i|G [@P ek& Iu. LNf 3~P
UrY uTA v=P MRc Rz] Wf, =0| hv0 o[/ 00R X/{ cL] xTg eI. <L7 }QO DS5 yg! 2\} _?|
AX` ;=1 m p b~! 4"y ?4T GIZ 5*e @]@ *,~ 1lY {0A >tl #V&  yZ xSr hr& r2B %TH aw8
EwR EUr w+U c{W H1t X,5 KlB r<$ a*^ AJJ i]_ '}! g%i $4: H#5 c`K ?W3 L&E ^%' &?/
iYq 6=& $1r "0f 0c9 5W% W`o %9~ BA2 TIV 4zY n[# )ZL Md\ aPf {ll s8Y LiB rjw yd.
H<p Gqn u_q uS4 >sD /&\ ^4[ L{N !=p 3E! N27 n?u BJ] ,*g m"W %_> hzY Xcd /1@ ^o^
|mw p38 $z, Sp* fzJ G#> YD@ +Mq C}s 3Sk svY a~; BrN -Nu $3{ V2> ^-. b[E IFk ?zX
eal X^\ 1#= m/[ *SU $8l K[W <Ms "G< 3=J Ps# !^b H(k ~pJ )5L iHp -Ss #KW 93Q $KZ
Lbf mfa il^ rb& -LW Q)* -6\ .m_ ,Yl Xqp ?-s X@B `jl F-\ &(% G|J Wxe 0`G ho2 G.7
Gkb T!9 qD} ZX, T,@ MS8 >EK WM( x!I #Z\ `0R x5> R 1 5O) g?A m?z 9 % g]o F/F ^B{
=qa X[L |rA X>w 3'F H1t 7@A SfJ OC% #?o ob/ Sxm ;Ed ?\^ IOe GY1 a2_ OW) 4Q. aS~
yD+ s3q )(v EOU 37= !N& (=9 ]Nj qJ< t#^ JEB Om` 1X% ^4m rL, I:8 b1+ k,' D|t N{u
Bn3 !$K 6}Q T'9 `^B CBD Bk: q:1 ,Mh ] C (_N *j* I+\ _"? }IR -hF 3;? )*[ G6o Ktn
=G4 ~!S UR; Al, :3Y ]BP PJ0 8rc [k, 8p8 z\V u}- )cP Z@8 6{+ Zox "Pe ;E* Mj: "Oz
*c5 qL* gIa H~s z'] #dy mNT Asb "m* zw: XXP  H( Vyq ii6 $Vi AOZ "u; 7c+ M<G X7q
5dH T)v OX( +t  'ac G$4 4JZ VJ) kxI Xww ^.E sa$ c<j Qc. ! X u[2 m9$ D2u f7e -"f
:?V yex +AN ~3W h8n .m" @>i LM+ qAk Tq3 w$+ 0Pz g+T ed  e#' a1s 6P% jy~ (V/ p-f
q G 7.\ Zdl yxg DI' |Au pY1 K=# #xu y73 rv; bs) Eo} m/% <a0 P8O 0]p 4n> jRz Hys
Dlx k2* ePU X,{ u$o gIx O1@ [dH yjh 8Bj t@^ uD| AHd =CT rCQ Pu9 J@e C.Y z<k *2F
$`j ^&z J2, cKg g}' d?. t;8 9T\ 6jZ ;v] 8am @-0 2"/ /GE *6  EPK hUa *cb T=b p~F
O&\ 6{k LO" l9: 25e SKS CKC gC; X9+ N.3 I~% ^Qs ,C, D_@ )xx 'G) wl4 KGq 6:X l9^
~^_ <nH sp$ f-t | z @i0 q>7 017 Yge BF*  +g 2d^ 1lU /Zr q"i c,J 4ys /UB Mk3 NSn
Lbg %,/ *'6 2sS 3t= 7(t C[A 9.x V*m P?m {Z9 4"U }_[ -mT \0~ S%, uu( 5=D ,Z/ OI<
fS+ C^) H"< Ki= $^9 OJ% Tav *Fe ,p1 n0" #Lh {<9 O=b r\* O\) +[M ?^x @o; FKs Jd}
ARc r+P : [ .AW $DC D*C ~i[ {sY q\p niX sv0 5tC x!w g4L MS[ \`@ uuq H`4 K": G~z
|R} o;< cP% P@N T@J &Z; dNu xLx /eB BIH e%] Hzy {1< F\( {!' _{[ kZ$ o&@ yAU J4C
k6  E>/ k?] E!w g~g u!> N6d vw% hp_ c)' /'w }*t ]H- dT6 067 S(/ a?. i=: tH? ,TE
B}\ K M 2ao qfd ~`@ +D@ Oqx eHG Px^  QA k4f *mR 0T\ $Fp ;ph /XZ M(1 5*b :Fd 5R5
a9@ .[s wZy >@4 @?S Qd1 K*S P]Y \ [ &I8 / 1 2PF mD- :"\ e9s ,Q) neb |0M M&k OKB
znw {h< wmU '~G ;S_ ;td ~}B a<{ +kB 8tS 0eS *tq 52T Q.j [QB (4M xI/ ~k- Z9M ^(V
fG^ 7'K _M1 94# pLo 9&/ p/j _'/ [ 4 GIF ~pi \/; JAz "6X n,A :/` %B9 E&s CCm 6j5
l`' GjY ,LH b"q zU[ wta QH8 W"H v{e usF 3qd lUK $aE KpF ]qm },> MDD y(9 _4< ]E^
Sd/ Xs5 }GD b30 >>3 (z. PW\ TQ) I|} I6D {5+ ; f ESA ,s< \`" W?Q cp| 5Mv /f+ 0/R
:k@ Y:e "R[ *uz [9~ KiT b_% &)e "uY S,G /`O m]C Y^h k6G yxo 2"' tpU Y?$ )ig 5h&
@r| a]L >hL $=N fAo >R| D=} a\: ]HH rC^ 1<z a_> k#j lA- a6Y lXW <X/ >UM *q> y}e
$o# ]]h [Tj #`i wyF }we k_$ <'I bor @o% UsX 7RL &NT .&+ 9D# /P. RQg akK <u  kp(
44o 8dq 3U( up% ur6 ^NP 9I- soH 5j@ 3-O :|; }Wc =;{ ?ng =,u we8 y^t BYW 'p| "aA
Pc% "Av ?Hv K_g xY;  m< Y%% %LA r@~ O|R cvW &X> xuf "h  {pt &/p ,)- 16_ m6$ GlI
DG1 P&T zB/ k@w &j)  8u I-R pcd Xvg W@Y  CF quE .5& (KZ :iK  CX [p: $<; :Z/ h:_
u"2 <(" b|5 p>d !^T 7z4 O-5 ^rK 4_5 jO* +FF y;; \/R wbw &5&  N7 Gdu 4m= `L/ .">
>Bt g?Y t_% S}w fD' sL3 N&M Lh^ Bn, 1_c }{" 4B\ }Dq {Qz Mjc ,N' b82 }5" ^.j [)Q
~z4 g@S 6_^ FKS {HM ^%=  W] mIY $Q- *J" c'_ _UO lZg 4vB _dh H6  7S7 HCt C*S ov"
Lk9 pyO  "q 7'# cq( kGL 20Z L>l 9WU 9-W )I> <u\ (v* w1g u9& 8;[ Z'9 w4^ OMh J\R
Cy> qnu ,wm ':D *wt -+a AOo ,>W ,Ao =hs HfR B[Z s3% }nv I9u L0L krZ g-B &O3 `MQ
I(q JF8 w Y gK^ ?Vi q:1 3Um qUv JHn skb  bL MQL {=L ;t) iba {(U ?eE d'( Prz pB;
0]W M$+ [WU $8' wP= 0DU %1$ B9m 5sG _li vi5 qeY F8| 0K- P|C nts Hmi _`) pub HFQ
U:Z yDo "LI 33{ }dm l.f xh5 ^>+ j*W b.B D$o non !F, /&+ ")Q [dk w$* ~*& N8; y?G
H6S pg= /<O j_o ;ZR 1@D t=` l\i )'@ D]+ xCl "0^ =rZ sn^ @,P awQ x!q 6C2 ;mP @Xf
AM( <CR _2Q \AC 46> ge2 7L  tBs X*% h00 9'x QYr $Cl jG;  8y *<\ e?O n2J pmS [%7
!mW |3g 3T, t+% `kk %=@ W | Mo8 Oa2 ?!d dwY =JO mA{ s<l N=` L89 @Z? Leo p>| ,YK
w+H %8s r@\ @I*  Tj m(! &gs Q&= Hf% 37i D+9 %Q' |6U ?*  lJ2 Q18 94: 3(L S?X Afj
m*A Qz~ Hd9 Tqn )=8 s?m }2' J(% qs% %i! eus ,hP n?p `qE 2P~ d#p d6n {m{ mHv @:K
h>z Q?% wG" :f" Vsl fb7 p3A J[( {|j ..t @Qx L@Q ;'n S<\ 6c* Mtc YGj I<x zD? PCk
>a" -!g W8S vCg Hoj SkL }|* ZCn 3G0 $Ih 8s6 xpG {zI cpz :V) PFr yaX fA] #I| B5V
du2 JYi hx1 <`U 5E& p~h =mw 5E3 SRz ;+, 3zP rX7 0lX <[$ Om= #_! &-N %Hm >cN yMq
I6T NjU h{m XH6 M$]  94 ;Up NNq  :; Bh+ Na+ <v' $"e Y]5 @s/ Qq2 UyN 3r? YsL \ii
IAX :LY }[( m30 }kY y7v L/v 8XM =U= Sbo Vsf <pZ i\? y(a NLF fU` 'xQ eI< '*t 9TY
G3K cZ& :2X x[; ;|O YPE zxL !qK I=Y 1`u 4tx E4E *k* CI2 Y|P @gl ff& )c- cx1 (]u
b7y ump ?}a ]Fn o+O }vC Iak 1:~ \Q% /[+ tW\ ^QO >#3 Am^ EUX ife idb H%w =.d Hzg
9U9 cvd Exq kSF {ss Spd &Ce \(D ZTp 6kS l!9 2XF 0Z+ N:b *r1 qXb r}E <cS D*d  +N
y2? ,xO 1nx lC. xVj myv P(_ k[Z *8} ;HT jU] sPm lYu b%l ka^ 4R{ :n$ D=F \5{ Cyi
nu4 VnA WxE Zl) ACp ~,* VXm 4rG *!w 6<A yBW L*t `N7 b$k 0;I gfn ]:n @1D e^W hn$
Wps 9H4 Q89 8w8 JTu 045 9E9 puU \P6 >&P wR4 <pH ^MF M}, GJW S7* 62i Rd: hyt P\p
]DR Bzj t}Y Sw* _N| \1[ kQG UB  Wv: [Xh PT( zs8 %Qm !6_ ]*^ WnQ /3r n|h 9NC wpx
6}3 t34 EQp :ZJ r|8 Blx C?W XN< ~]B 7.z 0OK m". C>j N09 RIV iEs 2(r @m_ v"_ ,N_
/]V L$? ~?L UDE `W/ f8` J1u qnB 'F6 &wH hrO xmd WuD )Z8 n ( "6B 59^ T/m WH~ $te
nE0 yLG .vi tM, 6'< N;H PsW 1Kc [#j oPh t|2 ?]< sja 8yV <@; `f1 Kxh {nm -5E Ic/
78~ n8K Y@s q[z iJ[ q\i Z0? rL7 8>T BV: >i~ 9.9 %Dm Y\C Bo- Dz0 b=9 xd, w{N AJf
at9 0~c E<I 49l Z{s fk9 |\@ 2HG 2O" 3 m 7cm Gj5 EaB M9~ .\2 naK +F, /j& *7?

OK, that's a mess. Let's filter those down to just the 560 ones that consist of just letters:

WiC laK fPi ELS rWf Iqg bdT DYU LzT lZF YNY yyp iRt Fyf DuZ ZJI QcX IDy Zmm dXl
YDF Pzu wpI hpg Qsp TZm tKK YlH nhs ECg AiH Ivn pac ivn yWg Bea jaM JIl kPH rMH
jST pSx cnp zuy QBK ewr ndh xBg wfd unB VDi WBm iBC IvG tID QNS sGx xOX ozM zwp
kcA kJd BMW rnx uni oQW cIN itz QFs Dwh QqV UnJ TLO aJC ukt kpX jRM kWM zIZ cVy
LQX AdG VLP hsg Slu CEu hNl olv XmZ Uus OUK hQN nzG KNk PaC edN Owa zju Ugx czs
TVb mpg llL soU Qyj vPF mYO sDq eVx DWN QeZ xjS wiD SPL zHn eaI Qzg BXa zjs Oxt
lnn JVc VOl QoK GPg edE WGC DRO FlN ssN pNL zmg rAv SES anf GOY xEi tHB zKl NUG
ity Kmj Esj DCl ORt TqK zOL AcT eCJ fQX khd iwv nGT rAQ Fyv QzQ GwW OSN Ixi ENP
sJb yhT lrk vaL wRz Zqz jIo IpB rJZ OLh GRY KCA VOC bcW Lym jno GPl Dew InF QPJ
qPt KJM ahV LuV tFx cWO SHs aEO lAy mHf rGt Hnq gUq qQC GyR bmV IHQ zWU Uym CbI
BWf zQD UTT hvU OOX hGd kXp jrj Buk fBO YMg tcQ nHG hIQ SeO yZa uGx eET BWC MZf
vjj zMl XVZ Hiz TAl kuS eBH exz fwV zRx JEa iSF hXJ Urk kwh gws qvJ pRB uSJ aMG
LiU GPX gFO iVp JEQ iyc VCZ NHG tBi qDX EUu FCg aGI nTX Qno kgk dmx oXT six EXh
Oni drv ysl IXv Gdp lvd UHL anv ijW qcV vCg JJv smc lvU vZg gvP BUY Kuv kMP gWR
tNZ ZMb XFR kEK qoA vUk Wvz qhI CmL gkb XSC NPC swH tkf CUR fFH LfA RDV Ces KQX
MXQ Cur Nti pHx Glq UIg kul mwS jJv kfS cgW lJk uJQ TLq dFv oPS eGo nyY EUo qaB
RLV YVC ZCH foC bCs kuu ZVx uyc XLc xQC Kqg ATZ War HDE LNf UrY uTA MRc xTg GIZ
xSr EwR EUr KlB AJJ iYq TIV aPf LiB rjw Gqn hzY Xcd fzJ svY BrN IFk eal iHp Lbf
mfa Xqp Wxe Gkb SfJ Sxm IOe EOU JEB CBD Ktn Zox gIa mNT Asb XXP Vyq AOZ kxI Xww
yex qAk Zdl yxg jRz Hys Dlx ePU gIx yjh AHd rCQ cKg EPK hUa SKS CKC KGq Yge NSn
Lbg Tav FKs ARc niX uuq dNu xLx BIH Hzy yAU qfd Oqx eHG wZy neb OKB znw wmU pLo
GIF JAz CCm GjY wta usF lUK KpF MDD ESA KiT yxo tpU fAo lXW wyF bor UsX RQg akK
soH BYW cvW xuf GlI pcd Xvg quE wbw Gdu Mjc FKS mIY lZg HCt pyO kGL OMh qnu AOo
HfR krZ qUv JHn skb MQL iba Prz qeY nts Hmi pub HFQ yDo non xCl awQ tBs QYr pmS
dwY Leo Afj Tqn eus mHv Vsl Mtc YGj PCk vCg Hoj SkL ZCn xpG cpz PFr yaX JYi SRz
yMq NjU NNq UyN YsL IAX Sbo Vsf NLF YPE zxL ump Iak EUX ife idb Hzg cvd Exq kSF
Spd ZTp qXb xVj myv sPm lYu Cyi VnA WxE ACp VXm yBW gfn Wps JTu puU GJW hyt Bzj
kQG WnQ wpx EQp Blx RIV iEs UDE qnB hrO xmd WuD yLG PsW oPh sja Kxh AJf EaB naK

Do any of those strings look like a plausible beginning for an English plaintext? Well, actually, a few do — just at a glance, I see Bea, Dew, War, Cur, six, anv, pac, RIV, CUR, BUY, etc. I'm sure there are plenty more that might be extended into a meaningful message, even if it's also clear that the overwhelming majority of three-byte strings are not meaningful English.

OK, but according to our unicity distance estimate, there shouldn't have been any reasonably English-like strings in the sample, or at least not more than one or two. So what went wrong?

Well, the main mistake we made is that the estimate of 1.5 bits of entropy per character is an average for long texts, and measures the entropy per character conditioned on the preceding text — that is, loosely speaking, it says that, given a piece of English text randomly truncated in the middle, you have about a $2^{-1.5} \approx 35\%$ chance of correctly guessing the next character after the break in the text.

However, the first character at the beginning of the message (or at the beginning of the fragment we're looking at) is much harder to guess, and thus carries a lot more entropy — I would guess somewhere around 4 bits, plus one bit for capitalization, if it's not known. The second character is also likely to be harder to guess than usual, due to the limited amount of context available, so let's randomly allocate it 3 bits, including the possibility that the capitalization might (or might not) change. (We could calculate more accurate entropy values from a suitable text corpus, but I don't happen to have one handy, so let's just go with these guesstimates.)

This leaves us only $8-5=3$ bits of redundancy for the first byte, and $8-3=5$ bits for the second one. Assuming that the following bytes have approximately the $8-1.5=6.5$ bits of redundancy assumed earlier, that means that, to uniquely determine a 16-bit key, we need $2 + \frac{16-3-5}{6.5} = 3.23$ bytes, which rounds up to $4$, not $3$.

So let's try the experiment again, this time with 4-byte strings. For brevity, I'll only show the 133 strings that contain only letters and spaces:

mDJP Ptwu wZIC fXRU OPht rmHg yXp  ffhC IqJl wocL mHxY jUqM reta XzRi EVRY IhIy
FtIB JZYV PhFP OpVy wrWe eoJf XwAN XtcF Bhmj Ipgx abFz MDCg ImqN ehbl Iafe zjfM
DaiH jaKu gQBF qkbi EoIo JzIb IAOT BhFI wYqZ uecv rHhy oKFP INHF WuQA GCmI InIO
YaHR lieX KfQw NzvY qPsn E Xn Xfxa AHyy OZFg qZFE FQsx ffje THPs djhU MFap xRqt
Pkwb cvsU UhfV frvF rfNN eiNt UxTt tTiV duLt MzPC rXUU YSOi vkxk URZj kzYZ RUNB
ZpyD UVpn ysFw temX IkcN UAaR sGDH HKhr YvXo QDSc KUr  YLCv cIjU MvOa eXWi Cqmg
Phed OTnf gbuV aJgL dVH  pabP l wz xNEF oVIv DWzL aUza dqMm ZQEh BcVZ vBTg nGsd
WcGs hUFW Vvrh qcEg RLhi NOuI vKkP KPsT rECZ yaKJ oSnU hkiO CKZN evJH BVJg vlVN
sYrM iXfM LoWf TxOv GNkP

At a glance, the only one of those strings that looks like a plausible start of an English word (let alone a message) is reta. EVRY and RUNB get close, but if we're going to allow such misspellings or run-on words (which, of course, a practical cryptanalyst should), then we really ought to increase our per-character entropy estimate to account for that.

In fact, one false positive is about what we should expect on average, if our sample length was reasonably close to the unicity distance. (This is true by definition, since the unicity distance is defined as the length of ciphertext needed to make the probability of a random incorrect key decrypting the ciphertext to a valid plaintext equal to one per the number of keys.) To reduce the expected number of false positives to a negligible value (say, 0.0001), we really ought to take a look at a couple more characters yet, and see if they still look like English.

$\endgroup$
  • $\begingroup$ Imagine having 30 blocks of cipher, each 16 bit and each having two English letters encrypted. How would you calculate the r? I am getting the correct plaintext only after decoding 7 blocks (14 chars). My r has to be almost 7 to justify the results... $\endgroup$ – spc16670 Feb 14 '15 at 22:47
  • $\begingroup$ Also, I do not quite understand the point about the short text. Although for the purposes of my experiment the text is short (60 chars) and therefore the point you are making is absolutely valid, I do not quite understand why the 2.46 calculation would not work for a long text. Perhaps there is a better way of calculating the unicity distance? $\endgroup$ – spc16670 Feb 15 '15 at 20:22
  • 1
    $\begingroup$ Honestly, I'm not sure what you're trying to say above. For your first comment, are you really saying that, even after decoding 12 bytes, you still get multiple plaintexts that look like plausible English text? As for your second comment, the point I was trying to make is that it's a lot harder to predict the first letter of a string than one of the later ones; the estimate of $r=1.5$ bits of entropy is only reasonable for those later letters. $\endgroup$ – Ilmari Karonen Feb 15 '15 at 20:40
  • $\begingroup$ (Quick example: I'm thinking of an English word; which letter does it start with? I bet you didn't guess that it's P! Now, the word continues with U, Z, Z; can you guess the next letter now?) $\endgroup$ – Ilmari Karonen Feb 15 '15 at 20:40
  • $\begingroup$ Now, to relate this to decryption, let's say you had the wrong key, and decrypted the first two letters as CH instead of PU; would this be enough for you to tell that the key is wrong? Now, what if, instead, you had already decrypted PUZZ, and got YR as the next two letters? Would you consider that as sufficient evidence to reject the key (or at least assign it a very low probability), even though the first four letters looked plausible enough? $\endgroup$ – Ilmari Karonen Feb 15 '15 at 20:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.