. -

- -

... _ 

REF ID:A569BB 

to IE WAIWDLiD IN .t..«01\D..t....'l\!Cli wa:i:w IRllCi 

b&Ws% '<i . ....._ ____ ~·,., 

Date: 23rd iFebrua:r,y, 1955 

Copy No.: ~I 

PL~B6~36/50 use 3605 

OOMMENTS ON !.JrSJJ D800 

it,-. Mr•L...-1 __ ___. 

Sucgarz 

This ptper describes the AFS .. '\Y D802, discusses certain 

features ot it and suggests two possible attaclcs. The validity 

at the attacks depends on the extent to uhioh the output o£ the 

del tamcxlulator can be cribbed, exactly or statistically. 

.__ ___ __,JNo. 97 

Distribution 

Standard. 

EO 3 . 3 ( h) ( 2 ) 

PL 86-36/50 use 3605 

eclassified and a roved for release b NSA on 06-11-2014 
REF ID:A569BB 

. ., . 

"Fe IE HillcNBl:EB IN AEEeRBiliNEE '•tfiTh 19'Slfii 

1. -----"'"'~To. 'fl 

• 

COMMFl'TTS OM 1'&.FSAY D802 

J31 MrJ EO 3 . 3 ( h) ( 2 ) 

PL 86-36/50 USC 3605 

PL86~36/5QUSC 3605 

References. 

1. Tentative Cryptosecuri ty Evaluo.tion or _'8:cr24 (X.:2} byl 

BRUSA C/s 146, A:91'il 28th 1952. ----

2. liS.i.\Y 4 (X-2) Low Echelon Ground Ciphany Syst$ BRUSA C/S 201. 

l.(cy 7th 19 52. 

3. DEY 804 byj I and.I I I IMo. 49. Oct.ober 

13th 1952. 

4. Tentative Cryptosecurity Evaluation of the iltemo.te CryptosysteJJ. 

for the lJ!SEi :0001. Issued/ by MS.A 412B-1. Jon.ua:ey 20th 1953. 

5. U.S. Cammmico.ticn Security Equipnents BRUS.\ C/S 237. August 1953. 

-,.;._-:=:"'-

~~ 

' \ fo. 91 

]\.. 

1\ 

,I 

'/I 

.. 

I 

•// # ..::- -
REF ID:A569BB 

TOP SECRET 

le BE lllcNBLEB IN2 :eee1tBlcNEE f """ llSICI 

T<Jo. '11 

- '•o stage a el• line (@) 

Q IQ ••• 39 liO 

JtO x 16 pl.ugboord 

c c 

kt I 

--- --~---

A = mod 2 addi tiai 

R = 16-lalgrendan walk ring 

a = al.arm circuit 

C = Converter 

Each ccnverter is at the f'orm 

a b c d 

x 

T 

c c 

• 1 

I 

EO 3 . 3 ( h) ( 2 ) 

PL 86-36/50 USC 3605 

where M = mul.tipl.::i.oa.tion an:l B = Boolean addition.Pi.a. x = ab + cd 

IN.//// FwleP ScCRET 

r o.'17 2. ,____ _____ __, 
llil REF ID:A569BB ., . 

TOP SECRET 

TO II! H*NOLl!D IN *CCOltDANCI! filTl1 lltSIG 

EO 3 . 3 ( h) ( 2 ) 

PL 86-36/50 USC 3605 

1. Introduction 

(a.) AFS .. \Y D804 ( f orncrly known o.s li.S..rr! 4 and IEY 804) , is a low echelon 

speech secrecy device. It wa.s designed and a.ssessed in refs 1, 2 ond 

3, m"ld it was concluded that the desi,gn offored ail.y a. low degree of 

security. ..\. mcxlifica.tion to this m.chine,, known ::is -~J1S.rcr: D802 

(f'omerly .i.US.~ D804. (X-4.)) is described and a.ssessed in ref' .4. This 

ncxli:f'ica.tion is desien,ed for t.olcphone circuits where a high degree of 

security is required. It is understood to be in use in smJ.l numbers, 

and will eventually be re:i;>J.aocd by li]'S!iY D801. 

(b) This pi.per desor.i.bes the machme, discusses certain features of it 

and sur;gests SOI!le rx>ssible lhles of atto.ok. 

2. Brief Descrintion 

• 

(a.) The equipnan.t is "push-to-talk!'. Speech is encoded on a deltaI'lodula.tor at 25 lees. :L cert3.in D.mOUn.t of' :roridor.i noise is fed into 

the systec. The me'fhod of' encitilermmt is sil:d.lar to thn.t of other 

ci:pher text autokey systeI!lS, om. Figure I should. be for the cost 

po.rt self'-expl.ana.tary. The main novel feature is the rondO!!l walk 

rings R1 and ~· R1 caisists of the i:nttem 1111001000110010, and 

steps one position if' sub-key ~ is 1i it' ~ is '1 it stands. ~ is 

drivEll. simil.arly by 1'2 and consists of 1he pa.ttem 1111001101000100. 

In an obV"ious noto.tiai, ~1 is derived f'rom Z1 •••• Z40 and is added 

to P41 to produce Z41. 

(b) The pllJ3boord is such tho.t adjacent points in the delo.y line Q cannot 

be mil ti:?;llied together. 

(c) Tho al.arms arc understood to be as f'ollows:-

(i) A5 and ~ (soc Fit,l\lro 1) arc du:plico.tcd. 

(ii) Counters count tho clistmico between the canf'igumt!m 11 :in the 

inputs and outputs at R1 and R2. If 'this exceeds 80 clements, 

transmission is cut off for 3(X) elements, so tha.t i:f' the 

condi ti.on persists th.ore is a nD.Sty buzz at both the send and 

receive end. This guards cgoinst fo.:ilurc of R1 or Dz, ccnatan'ti 

outp.it froo. A1 or~ and constant <J output f'rom A3 or .. \_, but 

not o.pparently o.gainst constant 1 output from A3 or ;i.J,.• 

(d) The first few hlmdred elements c£ enoh trans:r.dssiai are not tronsmitted ( ihe po.radax seems to be unavoidable). 

_____ ..... ~o. 97 
REF ID:A569BB -. 

"F9 BE I l~NBl:EB IN AeE6RBANeE • .. v1'fH IR918 

--- ---- --- -

Eci 3.3(h) (2) 

~1 86-36/50 USC 3605 

3. Notations 

The follawin3 notations are used in this pa!Jer. 

Q The liO-long delay line. 

Q1 The ith s~e :in Q. 

q• The la.st plll31led stage in Q. 

f The distance between Q

1 and Q40, i.e. Q

1 

= 'lz.o-t. It the :plugging is 

rondCEl the nedian wlue of f is 1 and the a:veraee value 1 • li2. 

Cl' The first plugged sto.ge in Q. 

R' The \:ring i.mich Q' helps to drive. 

R" The ring whloh cy• helps to drive. 

S Denotes 'sace' , when we are ca:ipa.ring ony two elements of the 

encipher~ process at dif'f'erent pasi tians at the text. 

D Denotes ' different 1 • 

P, K ond Z bear the.ir usuoJ. :r.MJ011infis of plain, key and cipier. 

4. S;ynchraniso.tion 

Mter 40 bits of cipher text have been ti:-ansmitted Q in the receiving 

equip:ient ''ill be identical with that in the send equipnent. The expected 

t:iLte of coal.escence of both the rondor.i wolk r.i.n,gs cru.1 be obto.ined by setting 

F(t) = 1 - .L in the forr.iulo. arj j?Jo. 36 Appendix I paragra.ph 6; 

this evaluates " to o.pprax::inntely 99.6 :positions. The expected . total. t:i.m for 

oaal.escence is therefore liO - f + 99.6 ~ 138 posi ti.ans. This has ignored the 

f oct that one ring con beg:in to coalesce one or two or so posi tians (according 

to the rll.U&1:ing) before the other con. 

5. Key 

The key is flat by mono bi ts but has a. slightly rough del ts. o.t distance 

c:ne; at higher distnnces the bulge decreases. See pa.ragra.ph 11 (c) for 

deta.ils. 

It is conceivable that the delta properties rm.y also be affected by 

particu1ar plue;g:ings; no work has been done to confirm th.is. 

,__ ___ ___,~o. 97 
REF ID:A569BB .. 

'F9 ·BE 1 IANBLEB IN ACCOltDANCI! W'IT11 lltSIG 

EO 3:3(hf1(2) 5111 

PL 86_=-_36/_~o u_sc __ 3,~6~0~5======================== 

7. Coalescence 

(o.) With suito.ble r/L rcpea.ts the probo.bility of two stretches of cipher 

text co::ll.escing a.t o.. given :position so a.s to fom a. ca.usal. cipher 

repeat soCl!ls to be approxir.ntely 2-48+£'. 

(b) The aotua.l process of coalesccmce is cOI:J!.'lex, a.s can be seen f'ra:i the 

f'ollOW":ing table. Imr:iedia.tely bef'orc coalescence occurs either Q 

r3J.Y be D (all previous stages a.re S), or Il' cay be off'set by one 

position either way (denote this by sa.y:izig tha.t R' is D) or both 

r.Ay be D, and in ea.ch ca.se P DAY be either S or D. The result ot 

such a. sto..te cay either be 

(i) tha.t both Z (i.e. ()) ::i.nd R' coal.esce, or 

(ii) tha.t Z (i.e. Q) cool.esces but R' does not or 

(iii) tha.t Z (i.e. Q) corn;pl.etely diverges. 

Compo.ri.son of two positions in the cipher 

text. Q ls S up to but not includ:ing C) • 

R' is either in phase (s) or of'f'set one Probabilities of results 

(D). The other ring is s. 

Sta.te 

I 

n 

Ill 

IV 

v 

VI 

(i) (ii) (iii) 

Condition of P/L Q' R' cml.es- partia.l divergence 

cence cool.cscenoe 

s s D 0 1 1 

2 2 I s D s 5/8 0 3/8 

s D D 0 t i 

2 

D s D 1/~ 1/~ 1 

2 

D D s 0 3/8 5/8 

D D D 1/4 1/4 t 

(o) Result (ii) f'rom states I, III and V will leave R 1 at an of'f'set of' 

one, i.e. at the next position nf text we shall have state I or IV. 

Result (ii) f'rom states IV and VI will ktave R' at an offset of two, 

which iuplies that it the P/L is D for the next two positions there 

is a l/16 chance of Q and R' coalescing; other ways of coalescing 

from such a state are of course possible but are less likely and 

would take longer. 

No.9 5. 
' I 

REF ID:A569BB 

TO BE HANDLED IN ACCORDANCE WI I H IKSIG 

=--==--==- ---=-=-=========-======= 

E:o 3:3\hTl2) 

PL 86-36/50 USC 3605 .__ _____ lNo. 97 

into a causal repeat. 

(b) Onoe sot-up, a1.1Ch repeats will onll' end when the P/L 

diverges. For the atto.ok to progress aey further we 

now nood soma lmOW"lBdge ot the P/L• It is not necessory 

to crib the t\vo texts ot a repeet but we must know whether 

the respective P bits Dl'C S or 'D in the positions succeeding 

the end of it. let us assume tho.t most ar all such repeats 

end as follows:-

P1• • • • 0 1 0 l 0 l 0 1 0 1. 0 l •••••• 

P2 ••• • 0 l 0 1 0 1 1 0 l 0 1 0 •••••• 

·~·· SSSSSSDDDDDD •••••• 

(c) It the repeat ends at tim 1, we shall have D at Qi at 1dim 2. 

If Q1 is\not plugged K will be S in all oases and we can ge 

on to time 3, 4 etc. until we find 'Q"• Now let us examine 

all pairs of' positions where there is D at "Q" and S at all 

subsequent stages. At 3/8 of these pairs K will be n. 

Examination of these pairs where K is D will iumediatoll' 

identity the other 3 stages plugged to the converter to 

which '

1

Q" is plugged. 

(d) We now take the 5/B x 1780 pairs where K is S and repeo.t 

the process on the second plugged stage in Q using on]S 

those pairs where the all.gnnent ot R" has not been affected 

by D at Q", and so on. 

(e) With luck we can recover most ot the plugging. In a less 

favourable case and with less than perfect lmowledge of 

the P/L we should get some wq.. If the machine has been 

partia.ll,y solved the amount of further work required is 

indicated below. 

Number ot converters 

solvod 

0 

l 

2 

3 

Approximate ave age number of distinct 

pluggings still to be tested 

I I 

1014. 7 

These figures give the order of reduction obtained. In practice 

secondar;y attacks would not assume all the remaining pluggings simultaneousl,y. 

____ ___.INo. 97 -6-
• 

REF ID:A569BB 

l'O Ii HANBl:EB IN AeeeL't:DA~CI! 'Wtl,... lltSIG 

Eb 3:3\hJ(Z) • - 7 -

PL 86-36/50 USC 3605 

(f') It is less oasy to E'.pply this attack to the beginning of' 

repents because of the random vro.lk rings. However, it 

wil.J. be seen from the table. in peragt"aph 7(b) tha. t 

coalescence will either arise from statellIV or VI at 

the very beginning of a P/L repeat or will arise from 

atate II in the middle of' such a repeat. If there is 

much silence the second method is more likely. In this case 

we shall have o. lnrge number of situations analogous to 

the end-of-repeat situations discussed above, end the same 

sort of attack will appp13. 

(g} The WF consists m&.inJ.y9or the initial sort for causal cipher 

repeats, and, Since 10 is an outside estimate of ~e 

nmnber 09 bits req~, will be less than about lD 

(log2 lO -1) = 10 • sorting operations. 

9. Statistical Attacks 

(a) These require statistical cribbing of' the delta of the plain 

text at distance one. It does not matter whether the aribbed 

bits are consecutive ~ not. The number of assumptions 

required depends on the amount of' arib available. N.,te A 

describes two attacks: 

.Anount of exact delta crib needed 

a.29 . lO bits = 129 minutes' transmission 

m5•

16 bits= 5.7 seconds' transmission 

Work Factor 

10.8 . lO operations 

13.9 . 10 operations 

These are the outside figures. Others can be suitablif 

interpolated between them. 

(b) If the available cn:ib is not exaot but stctistical tlOl"e text 

is needed and the WF is correspondingly larger. See paragreph 

14 far a general discussion of CI'l.bbing f~r these attacks. 

(c) '1'he statistical attacks are only possible because the r ondoc 

\'lallc rings step "O and l"• If it was impossible for them 

to hesitate - if they ste.t>,ped 111 and 2" for instance -

the attacks would be complete4" blocked. 

JD. SUJJJID!lrY 

This paper has considered, somewhe..t aca.demicalJ,y, 'bi10 attacks. 

Both ~end tar their effectiveness on the properties of' the plain text. 
. ... 

INo. 97 

REF ID:A569BB 

... TOP SECRET 

le IE I IAN8Ll!8 IN ACC01t8ANCI! WI I H IKSIG 

- 8 -

EO 3 . 3 ( h) ( 2 ) 

PL 86-36/50 USC 3605 
REF ID:A569BB 

EO 3.3Jh) (2) 

PL 86-36/50 U$C 3605 . 

• 2 • 

40 stage delay line (Q) 

liO x . 1 6 plugboO±q. 

c c 

A = mod 2 addition 

R = 16-lor:igrandom walk ring 

a = alarm circuit 

C = Converter 

Each ca11verter is of the form 

a . b c 

\!/ 

x 

d 

L....-___ ..... 110. 97 

c c 

I! 

I 

, I 

I 

'' 

> 

where M = multi.plication and B = Boolean ··addition, i.e. x = ab .+.c4: + '9-Pcd~:. 

(Mod 2). 

.__ ___ __.IN o. 97 

·Figure I 

2. 
REF ID:A569BB 

IO BE "A1111DLl!D IN AeeeRBlcNGI WITl:I llSIG 

- ---=---=====~======~~~== EO 3 . 3 ( h) ( 2 ) L.....-__ ___.ro· 21 

PL 86-36/50 USC 3605 

NOTE A 

STATISTICAL ~TTJ.CXS 

11. Properties at the Corabining Systc~ (see Figure l) 

(a) The converters 

(i) If a is ¢, p(a = x) = i(l + i) 

It a is l, p(a = x) = i(l + 1/4) 

where p(H) is the probubility that H is true. 

Sicilarly tor b, o and d. 

The average probability therefore is 

p(a = x) = i(l + 3/8f; 

\ 

(ii) It a = b = ab = l, p(ab = x) = i(l+~) 

if ab = ¢, p(ab = x) = i"{l. + i~ 

Similarly for the pa:ir c,4. 

The average probability therefore is 

p(ab = x) = i(l + 5/8). 

(iii) It a = c = ~ p(ac = x) = i(l + 1) 

1 1 

If' a = c = l, p(ac = x) = 2(1 + 2) 

I.£ a + c = 1, p(ac = x) = i(l + 0) 

Similarly for the pairs a,d; b,o; b,d., 

The a.vero.ge proOO.bUity therefore is 2(1+3/8). 

(iv) if one input to a conTcrtar is recovefed the probe.bility 

that the output reJJ&.ins im.ohangcd is 2(1 + l/~) 

(b) The random walk rings 

If r is the output of a ring at tice i, i 

) 

1 1 p(r. = r. 1 = 2 (1 + 2) 1 1 + 

p(ri = r 1 + 2) = 1/4 + i • i + 1/4.. 3/8 = i(l + 3/16) 

(c) The key 

The :rinal key is flat by monobil;s. 

I No. 97 -9-
REF ID:A569BB 

19 IE HAM9l:EB lN AEE91\BANC£ t . .':ffH 1Ml6 

NOTE A 

• (K 1 8 2 8 

p i = x1 + i> = 2(1 + (! ) (i) ) = i (1 + ur7· 3) 

8 

1 8 2 8 7 and p(Ki = K. 2) = 2 (1 + (! ) (3 ) ) =- i (1 + 10- • 1) 

1 + 8 16 

No. 97 - 10-
• REF ID:A569BB 

!() IE t:IAMDLED IN •CCORDAN(F WIJH !RS!G 

--============== 

EO 3~3(h)\2! - 11 - PL 66-36/50 USC 3605 I No. 97 

No. 97 - 11 -
REF ID:A569BB 

10 BE HANDL.ED IN ACCOltDANeE '#ITH lislCi 

-----

~~- -~· ======================================================== --=-

16. 

- 12 - I ,...., 

Other cethods EO 3.3(h) (2) 

PL 86-36/50 USC 3605 

(a) Tho forego:i.ne; has desaribed only 2 particular attacks, where 

4 lllld 8 pomts ore assumed respec:t:lvely. It is of course 

equally valid to s.ssWJE 5, 6 or7 points, according to the 

amount of arib avaikble on a given day. Unless crib is 

vary hard to come by, it/is probably not economical to 

assLU'lle c. 3rd lllput t() a. converter. 

(b) In pt"'.ragraphs 12 snd 13 vie required sufficient text each tine 

to prove or disprove each plugging assumption. ~7e could 

alternatively have run£!! plugging assu~tions through a 

shorte~ stratch of text, and combined the answers. This 

method. would 1n0identtlly recover the whole plugging a~me~ 

...._ ____ __... : N~. :;· [~ \ I ;::?j ~--

r . 

' L> ~ ~~ ....