• DES Planung, 20. 02. 1990
• DES Modifikation und Einsatz auf dem EC 1834 (KRAKE)
• Klassen von Blockchiffrieralgorithmus, 03.09.1990
• LAMBDA-1, 04.04.1990
• Sachbestandsbericht LAMBDA-1
• Blockchiffrieralgorithmus DELTA, Entwicklungsstand, 28.04.1990
• Vorläufige Beschreibung DELTA, 10.04.1990
• Grafische Darstellung von DELTA
• Laufzeitbetrachtung von DELTA gegenüber DES, 12.07.1990

Möglichkeiten und Gefahren der Nutzung des DES - erste Fassung

                            Einleitung

Die Darlegung bewegen sich in folgenden Rahmen:

1) Nutzung des DES zur Geheimhaltung von Informationen.
Betrachtungen im Zusammenhang mit weiteren Formen des
Informationsschutzes wie z. B. Identifikation.
Manipulationsschutz werden bewußt weggelassen. Sie würden hier
und da einige Modifikationen im Text erfordern, die den Text vor
allen verlängern würden, ohne prinzipiell, quantitativ Neues
einzubringen.

2) Nutzung des DES durch die bzw. in der DDR für Informationen,
die keine Staatsgeheimnisse darstellen. Also z. B. Nutzung zur
Speicherung von Personendaten in einem Krankenhaus, zur
Informationsübermittlung zwischen Betriebsteilen eines VEB, in
einem Chiffriermodul für evtl. auch zu exportierenden
Personalcomputer.
Diese Beschränkung ist bei einigen Aussagen durchaus
wesentlich.

3) Zeitrahmen: Die Aussagen sind nicht für 10 Jahre ausgelegt.
Sie beziehen sich bewußt auf die Gegenwart und die nahe Zukunft.

4) Weglassen aller Fragen des Schutzes gegen technische und
Bedienfehler, gegen Kompromittierung des Schlüssels u. dgl.

Leserkreis: Diese Ausarbeitung ist in der vorliegenden Fassung
nur für Mitarbeiter des ZCO gedacht, die eine dienstliche
Beziehung zum Thema haben.
Es kann überlegt werden, ob eine modifizierter Text für die
Öffentlichkeitsarbeit verwendet werden könnte. Dafür wäre
aber noch mindestens die Mitwirkung kompetenter Spezialisten und
eine solide Quellenarbeit erforderlich.

Terminologie: Mangels neuerer, verbindlicher und allgemein
verbreiteter Terminologie werden die kryptologischen Termini im
Sinne der Fachbegriffe des Chiffrierwesens des ZCO der DDR von
1971 benutzt.

1. Kurzbeschreibung des DES
Basis - Algorithmus:
      64 Bit (=Grundeinheit) --> 64 Bit (=Geheimeinheit)
      Folge von Operationen, die 16mal wiederholt wird.
      Schlüssel 56 Bit
Um den DES anwenden zu können, muß der Klartext
(Fernschreiben, Daten, Sprache, …) in eine Bitfolge umgeformt
werden. Sie kann völlig beliebig strukturiert sein. Sie wird in
Blöcken der Länge 64 Bit (Grundtext = Folge der
Grundeinheit) chiffriert. Als Geheimeinheit zu einer gegebenen
Grundeinheit kann - schlüsselabhängig - jeder beliebige 64 -
Bit - Block entstehen.

DES ein einfaches Tauschverfahren, wobei die verwendete
Substitution 2⁶⁴ Grundeinheiten enthält.
Randnotiz // als einfache Tauschverfahren nicht für beliebig
          //strukturierte Texte zulässig! s. u. Km

Arbeitsregime:
Es sind verschiedene Arbeitsregimes des DES bekannt. Sie
gestatten u. a. die Nutzung des DES (des Basisalgorithmus) zur
Additionsreihenerzeugung unter Nutzung eines Spruchschlüssels,
bei Verwendung des im Basis - Algorithmus benutzen Schlüssels
als Zeitschlüssel, sowie die Realisierung rekurrenter
Verfahren.

2. Geschichte des DES
Der DES wurde in den 70er Jahren in den USA entwickelt. Er war
das Produkt mehrjähriger Arbeit vieler sachkundiger Experten,
einschließlich Mitarbeiter der NSA. 1977 wurde er offizieller
USA-Standard für Banken, Konzernen und sonstigen nichtstaatliche
Institutionen aller Art. Der Standard wurde ohne irgendwelche
Geheimhaltungsbeschränkungen veröffentlicht. Es kam zu einem
breiten Einsatz des Standards in den o. a. Institutionen, auch
außerhalb der USA, der bis heute anhält.
Über den Einsatz des DES für Staatsgeheimnisse in USA-
Staatsorganen ist nicht bekannt.
Randnotiz // er ist nicht zugelassen Km

Der DES erweckte und erweckt bis heute das Interesse vieler
Wissenschaftler als interessantes Forschungsobjekt. Es gibt eine
Fülle von Veröffentlichungen auf wissenschaftlichen Tagungen
und in wissenschaftlichen Zeitschriften bzw. Büchern über die
Eigenschaften des DES als mathematisches Objekt. Es ist jedoch
keine Veröffentlichung bekannt, aus der sich ein
Dekryptieransatz ableiten ließe, der deutlich effektiver als
die TPM (Totale Probiermethode) sein könnte.
Es ist bekannt, daß die NSA sich intensiv mit dem DES
beschäftigt hat. Es ist unklar, ob die NSA eine
Dekryptiermethode kennt, die wesentlich effektiver als TPM ist.
Die gleiche Aussage kann für die 8. HV getroffen werden.
Seit einigen Jahren gibt es in den USA Arbeiten zur
Bereitstellung eines Nachfolgers für DES. Er wird als Chip
bereitgestellt. Der implementierte Chiffrieralgorithmus wird, im
Gegensatz zum DES, geheimgehalten, indem durch technische
Maßnahmen seine Rekonstruktion aus dem Chip verhindert werden
soll.
Randnotiz // Chip zwei Nachfolger

3. Eigenschaften des DES, Sicherheit
56 Bit für den Schlüssel sind heute wenig. Es ist vorstellbar,
daß die leistungsfähigsten Dekryptierdienste der Welt, unter
Nutzung aller Möglichkeiten von Wissenschaft und Technik
(Spezial- Hardware, Parallelisierung, …), mit einem an die
Grenzen ihrer Fonds gehenden Aufwand die TPM realisieren.
Es ist unbekannt, ob diese Dekryptierdienste Gesetzmäßigkeiten
des DES kennen, die - unter irgendwelchen, realen Annahmen und
Voraussetzungen - wesentlich weniger Aufwand als das
Durchprobieren von2⁵⁶ Varianten erfordern.
Der DES enthält keine Bestandteil, der als LZS verwendet
werden könnte. Hier kann nur durch Modifizierung abgeholfen
werden.
Der DES als einfaches Tauschverfahren realisiert von der
kryptologischen Klassifikation her eine der einfachsten Formen
der Chiffrierung. Ihre Schwäche besteht vor allem darin, daß
die Häufigkeitsverteilung im Klartext durch die Chiffrierung
nicht verändert wird. Beim DES ist diese Eigenschaft zur
Dekryptierung nutzbar, wenn sich im Grundtext (=Folge der
Grundeinheiten) eine ausgeprägte ungleichmäßige Häufigkeit
einstellt. Das ist in der Praxis aber nur in extremen
Sonderfällen vorstellbar und sollte durch zielgerichtete
Maßnahmen bei der Herrichtung des Klartextes immer vermeidbar sein.
Randnotiz // ?

Die in der Literatur angegebene Arbeitsregimes des DES
überwinden diese Schwäche wirksam.

Zusammenfassung: Der DES gewährleistet hohe Sicherheit für die
Geheimhaltung von Informationen. Durch geeignete Gestaltung
der Einbettung des DES in seine Umgebung kann unter beliebigen
Anwendungsbedingungen erreicht werde, daß aus den aus der
offenen Literatur bekannten Eigenschaften des DES kein
Dekryptieransatz abgeleitet werden kann.

ACHTUNG! Das ist nicht die Aussage, die für den Anwender
wünschenswert ist. Diese Aussage - es ist beweisbar, daß es
keine Dekryptieransatz gibt - kann nicht getroffen werden, und
es ist kein Weg erkennbar, auf dem man zu dieser Aussage
gelangen könnte.

4. Realisierungen
Bereits kurz nach Veröffentlichung des DES als USA-Standard
kamen die ersten DES-Chips auf den Markt. Diese Tendenz hat
sich, in voller Analogie zur generellen Entwicklung der
Elektronik in der Welt, ständig fortgesetzt.
Ebenfalls gibt es in der Literatur immer mehr Programme zur
schnellen DES-Realisierung auf unterschiedlichen Rechnern und in
unterschiedlichen Betriebssystemen.

5. Möglichkeiten der DES-Modifizierung
Diese Thematik ist unerschöpflich. Soll im Hinblick auf eine
konkrete praktische Anwendung in dieser Richtung gearbeitet
werde, dann ist dringend zu empfehlen, nach den bewährten
Grundsätzen zu verfahren, die bei Entwicklungsarbeiten
allgemein üblich sind. Insbesondere ist konkret
herauszuarbeiten:
 - was soll erreicht werden?
 - was soll vermieden bzw. verhindert werden?
Der Spielraum wird sofort entscheidend kleiner, wenn eine
Forderung lautet, bestimmte Eigenschaften gezielt zu verbessern,
wobei zu garantieren ist. daß bestimmte andere Eigenschaften
nicht schlechter werden.

Eine mögliche Systematisierung der Modifikationsrichtungen ist:
(1) Änderung innerhalb des DES
Beispiel: Variable Gestaltung der Eingangspermutation und deren
Verwendung z. B. als LZS.
Es gibt für 64! Möglichkeiten. Damit ist TPM ausgeschlossen.
Bei Gewährleistung ausreichender Unregelmäßigkeit der
Grundeinheit ist intuitiv kein Dekryptieransatz erkennbar,
wenn sowohl Schlüssel als auch Eingangspermutation unbekannt
sind.
Randnotiz // beachte Chosen-Plaintext-Angriff: Vergleiche neuen
          // Alg./Original-DES bei gleichen Schlüssel
          // und Chiffr. Einheitsvektoren als KT Km

(2) Kombination des DES mit sich selbst
Beispiel: Auf die Grundeinheit wird DES mit Schlüssel S1
angewendet. Der entstandene 64Bit-Block wird mit DES mit
Schlüssel S2 noch einmal chiffriert.
Das bedeutet eine Erhöhung des Schlüsselvorrates von 56 auf 112
Bit, was TPM ausschließt. Bei Gewährleistung ausreichender
Unregelmäßigkeit der Grundeinheit ist intuitiv kein
Dekryptieransatz erkennbar, wenn sowohl S1 als auch S2 unbekannt
sind.

(3) Kombination des DES mit weiteren Verkomplizierungen
Beispiel: Kombination des DES mit Teilen eines anderen
Chiffrieralgorithmus.
Hier ist alles Mögliche denkbar. Es muß die Gefahr
ernst genommen werden, daß sich irgendwelche
sicherheitsrelevanten Eigenschaften verschlechtern; die
Untersuchung dieses Problems könnte sehr aufwendig werden.

(4) Kombination von (1) - (3)

5. Zusammenfassung
(1) Der DES bietet hohe Sicherheit. Es kann aber nicht
ausgeschlossen werden, daß es Dekryptierdienste gibt, die - mit
hohem Aufwand - den DES dekryptieren.
Wenn ein Nutzer einschätzt, daß seine Informationen nicht so
wertvoll sind (im Vergleich mit Informationen anderer Nutzer in
alle Welt), daß diese Dekryptierdienste diesen hohen Aufwand
treiben werden, dann kann er seine Informationen mit dem DES
geheimhalten. Die Sicherheit seiner Informationen liegt dann
voll und ausschließlich in der Geheimhaltung der Schlüssel.

(2) Die Schwachstellen nur 56 Schlüsselbit und kein LZS
können im Ergebnis gezielter Entwicklungsarbeiten für konkrete
Anwendungsbedingungen überwunden werden.

(3) Die praktische Realisierung des DES bzw. von Kombinationen
und Modifizierungen ist für sehr viele Anwendungsbereiche mit
vertretbaren Aufwand möglich.

Einsatz des DES Verfahrens für den EC 1834/DCP (PC)
Das DES Verfahren wurde als Softwarelösung, mit den Namen KRAKE, für den
EC 1834 ab dem Jahr 1990 entwickelt und eingesetzt.
Weitere Erkenntnisse und Erfahrungsberichte aus dieser Zeit liegen noch nicht vor.

     Abteilung 2                   Berlin, 3. September 1990


     G r u n d s ä t z e
     für die Entwicklung einer neuen Chiffrieralgorithmenklasse

     1. Es sind Algorithmen bzw. Algorithmenklasse für Staatsge-
        heimnisse (Geheimhaltungsstufe Geheim) zu entwickeln.

     2. Ein breites Einsatzspektrum ist anzustreben. Damit sin die
        Algorithmen der Klasse so zu gestalten, daß sich für even-
        tuelle Dekryptierangriffe praktisch verwertbare Informationen
        nicht auf Bereiche auswirken können, in denen andere Algo-
        rithmen der Klasse eingesetzt sind (Einbau vom LZS)

     3. Zu entwickeln ist ein 64-Bit Blockchiffrieralgorithmus gemäß
        ISO 8372. Damit sind Schnittstellen und Betriebsarten vom
        Grundsatz her definiert.

     4. Für die Entwicklung des Blockchiffrieralgorithmus sind die
        bewährten Forderungen für solche Algorithmen, (vgl. DES
        Konstruktionsprinzip) wie Confusion, Diffusion, Ähnlichkeit
        von Chiffrierung und Dechiffrierung einzuhalten.

     5. Die perfekte Sicherheit im Sinne von Shannon muß nach einer
        gewissen Mindestanzahl von Runden erreicht werden, wenn ein
        on linie Schlüssel zur Anwendung kommt.

     6. Der Algorithmus muß sowohl für Softwarerealisierung in
        Universalrechnern als auch für Spezialgeräte (Hardware,
        Software und Kombinationen) günstig realisierbar sein.

     7. Bzgl. Speicherplatz und Zeitverhalten müssen ähnliche Werte
        erreicht werden wie mit dem FEAL Algorithmus oder dem von
        Massey zu EUROCRYPT 90 vorgeschlagenen Algorithmus.

     Es gelingt nicht klare Geschwindigkeitsanforderungen zu formulie-
     ren da diese immer von der Hardware abhängig sind.

     gewisse Schallgrenzen liegen bei

          9,6 Kb/s
         19,2 Kb/s
         48,0 Kb/s
         64,0 Kb/s (ISDN Kanal)


     Quellen

     - ISO 8372 First edition 1987 - 08 - 15
       Information processing - Modes of operations for a 64-bit block
       cipher algorithmus

    - Kongressmaterial EUROCRYPT 90

    - Fumy, Rieß Kryptographie, R. Oldenbourg Verlag 1988

LAMBDA 64bit Blockchiffrierung

BESCHREIBUNG LAMBDA1 vom 04.04.1990

1. Einleitung

Der hier beschriebene Algorithmus LAMBDA1 kann in den stan-
dardisierten Arbeitsmoden für 64 - Bit -Blockchiffrier-
algorithmen gemäß ISO 8372 angewandt werden.
Mit der LAMBDA1 Beschreibung erfolgen zugleich verbindliche
Vorgaben für weitere Darstellungsvarianten des Algorithmus.

LAMBDA1 wurde aus dem DATA Encryption Standard DES abgelei-
tet. Folgende Änderungen wurden vorgenommen:
- Vergrößerung der effektiven Schlüssellänge von 56 Bit
  auf 256 Bit;
- Änderung der Art und Weise der Schlüsselfolgenerzeugung;
- Addition zweier Schlüsselvektoren nach 8 Verarbeitungs-
  zyklen;
- Änderung der Anfangspermutation IP.
Zur Anpassung an vorgesehene Realisierungen wurden gegenüber
der DES-Beschreibung eine leicht modifizierte Darstellung gewählt.

2. DEFINITIONEN

2.1. Bezeichnungen

Es sei Vm=:{0,1}m, m ∈ N, die Menge aller m-Tupel von Elemen-
ten aus {0,1}. Die Komponentenschreibweise für X ∈ Vm:
(X(1), X(2), …, X(m) ).

Operationen über Vm:
⊕: Vm x Vm→Vm ∀(X, Y, Z) ∈ Vm3:
     X ⊕ Y = Z ⇔ ∀ j ∈ 1,m: X(j)+Y(j) ≡ Z(j) (mod 2).

"": Vm x Vm → Vm ∀(X, Y, Z) ∈ Vm3:
     X  Y = Z ⇔ X(1)•2m-1+ X(2)•2m-2 + … + X(m)•20+
                  + Y(1)•2m-1 + Y(2)•2m-2 + … + Y(m)•20 ≡
                  ≡ Z(1)•2m-1 + Z(2)•2m-2 + … + Z(m)•20(mod 2m).

"": Vm x Vm → Vm  ∀(X, Y, Z) ∈ Vm3:
     X  Y = Z   X = Z  Y.

Es gilt: ∀(X,Y) ∈ Vm2:
         X  Y = X (0,0, …,0,1)  (Y⊕(1,1, …,1)). (*)
(Im folgenden wird das jeweilige m aus dem Kontext ableitbar sein.)

Abbildungen:

E: V32 → V48  ∀ X ∈ V32:
E(X(1),X(2), …X(32)) =: (X(32),X(1),X(2),X(3),X(4),X(5),X(4),
X(5),X(6),X(7),X(8),X(9),X(8),X(9),X(10),X(11),X(12),X(13),
X(12),X(13),X(14),X(15),X(16),X(17),X(16),X(17),X(18),X(19),
X(20),X(21),X(20),X(21),X(22),X(23),X(24),X(25),X(24),X(25),
X(26),X(27),X(28),X(29),X(28),X(29),X(30),X(31),X(32),X(1)).

T: V48 → V48  ∀ X ∈ V48:
T(X(1),X(2), …,X(48)) =: (X(48),X(1),X(2), …,X(47)).

S=S(S1,S2, …,S8): V48→V32 wobei ∀ j ∈ 1,8: Sj: V6→V4.

Für beliebige X= X(1),X(2), …,X(6)) ∈ V6,
              Y= (Y(1),Y(2),Y(3),Y(4)) ∈ V4 und J ∈ 1,8

gilt Sj(X) = Y genau dann, wenn in der j-ten Tabelle in der
Ziele Nr. X(1)2 + X(6) + 1 und in der Spalte Nr.

   X(2)8 + X(3)4 + X(4)2 + X(5) + 1 der Wert
   Y(1)8 + Y(2)4 + Y(3)2 + Y(4) steht:

                      S1
14  1 13  1  2 15 11  8  3 10  6 12  5  9  0  7
 0 15  7  4 14  2 13  1 10  6 12 11  9  5  3  8
 4  1 14  8 13  6  2 11 15 12  9  7  3 10  5  0

                      S2
15  1  8 14  6 11  3  4  9  7  2 13 12  0  5 10
 3 13  4  7 15  2  8 14 12  0  1 10  6  9 11  5
 0 14  7 11 10  4 13  1  5  8 12  6  9  3  2 15
13  8 10  1  3 15  4  2 11  6  7 12  0  5 14  9

                      S3
10  0  9 14  6  3 15  5  1 13 12  7 11  4  2  8
13  7  0  9  3  4  6 10  2  8  5 14 12 11 15  1
13  6  4  9  3 15  3  0 11  1  2 12  5 10 14  7
 1 10 13  0  6  9  8  7  4 15 14  3 11  5  2 12

                      S4
 7 13 14  3  0  6  9 10  1  2  8  5 11 12  4 15
13  8 11  5  6 15  0  3  4  7  2 12  1 10 14  9
10  6  9  0 12 11  7 13 15  1  3 14  5  2  8  4
 3 15  0  6 10  1 13  8  9  4  5 11 12  7  2 14

                      S5
 2 12  4  1  7 10 11  6  8  5  3 15 13  0 14  9
14 11  2 12  4  7 13  1  5  0 15 10  3  9  8  6
 4  2  1 11 10 13  7  8 15  9 12  5  6  3  0 14
11  8 12  7  1 14  2 13  6 15  0  9 10  4  5  3

                      S6
12  1 10 15  9  2  6  8  0 13  3  4 14  7  5 11
10 15  4  2  7 12  9  5  6  1 13 14  0 11  3  8
 9 14 15  5  2  8 12  3  7  0  4 10  1 13 11  6
 4  3  2 12  9  5 15 10 11 14  1  7  6  0  8 13

                      S7
 4  1  2 14 15  0  8 13  3 12  9  7  5 10  6  1
13  0 11  7  4  9  1 10 14  3  5 12  2 15  8  6
 1  4 11 13 12  3  7 14 10 15  6  8  0  5  9  2
 6 11 13  8  1  4 10  7  9  5  0 15 14  2  3 12

                      S8
13  2  8  4  6 15 11  1 10  9  3 14  5  0 12  7
 1 15 13  8 10  3  7  4 12  5  6 11  0 14  9  2
 7 11  4  1  9 12 14  2  0  6 10 13 15  3  5  8
 2  1 14  7  4 10  8 13 15 12  9  0  3  5  6 11

2.2. Abbildung G

G: V32 x V48 → V32 ist für eine gegebene Permutation

P: 1,32→1,32 folgendermaßen definiert:

∀ (X,Z) ∈ V322 ∀ Y ∈ V48:  G(X,Y) = Z genau dann, wenn
Z = S(Y⊕E(X(P(1)),X(P(2));…,X(P(32)))).

Vorläufige Variante für P:

Bemerkung: Die Abbildung G unterscheidet sich in ihrer Wirk-
kungsweise von der Abbildung f der DES-Beschreibung.
(Anwendung von P an anderer Stelle).

2.3. Schlüssel

B = (B(1),B(2), …,B(256)) ∈ V256 sei der verwendete Schlüssel.
Daraus werden die folgenden Vektoren gebildet:

K1=: (B(1),B(2), …,B(48)) ∈ V48
K2=: (B(49),B(50), …,B(96)) ∈ V48
K3=: (B(97),B(98), …,B(144)) ∈ V48
K4=: (B(145),B(146), …,B(192)) ∈ V48
∀ j ∈ 5,12: Kj =: T11(Kj-4)
∀ j ∈ 13,16: Kj =: T11(K25-j)
K17=: (B(193),B(194), …,B(224)) ∈ V32
K18=: (B(225),B(226), …,B(256)) ∈ V32.

2.4. Die Folge (Lj,Rj), j=0,1,2, …,16

Für gegebene (L0,R0) ∈ V322 wird definiert:
∀ j ∈ 1,16: Lj ∈ V32∧Rj∈V32

∀ j ∈ 1,16:	{	(Lj,Rj) =: (Rj-1,Lj-1⊕G(Rj-1,Kj))   j ∈ {8,16}
		(L8,R8) =: (R7K17,(L7⊕G(R7,K8))K18)
		(L16,R16) =: (L15⊕G(R15,K16),R15).

2.5. Die Gesamtabbildung und deren Umkehrung

Es sei A = A(1),A(2), …,A(64)) ∈ V64 ein umzuformender
64-Bit-Block. Im Ergebnis der Gesamtabbildung entsteht
daraus der 64-Bit-Block C = (C(1),C(2), …,C(64)) ∈ V64.
Es sei (L0,R0) =: A.
Bilden (Lj,Rj für J=1,2, …,16 gemäß 2.4.
Dann ist C = (L16,R16).
Umkehrung: Es sei C = (C(1),C(2), …,C(64)) ∈ V64 gegeben.
Bilden (L′0,R′0) =: C und
∀ j ∈ 1,16: K′j =: K17-j
K′17=: (0,0, …,0)K18=(*)(0,0, …,0,1)(K18⊕(1,1, …,1))
K′18=: (0,0, …,0)K17=(*)(0,0, …,0,1)(K17⊕(1,1, …,1)).

Berechnen analog zu 2.4.:

∀ j ∈ 1,16:	{	(L′j,R′j) =: (R′j-1,L′j-1⊕G(R′j-1,K′j))   j ∈ {8,16}
		(L′8,R′8) =: (R′7K′17,(L′7G(R′7,K′8))K′18)
		(L′16,R′16) =: (L′15G(R′15,K′16),R′15).

Dann erhalten wir A = (L′16,R′16).

3. Skizzen

Die Skizzen sind kein Bestandteil der Definition.
Sie sollen lediglich den Ablauf der Umformungen veranschau-
lichen

I. Verallgemeinerung der DES-like function für LAMBDA1

I.1. Allgemeine Bezeichnungen und Definitionen

a) Vn - Vektorraum der Dimension n über GF(2)

b) Sx - Gruppe aller Permutationen über eine Menge X

c) Ax - Gruppe aller geraden Permutationen über eine
           Menge X (alternierende Gruppe)
d) k-Funktion auf Vn

   Eine Funktion ς folgender Gestalt

   (a1, …,aik+1,.., an) ς =
   = (a1, …,aik+1f(a1, …,aik), …,an)

   heißt k-Funktion.

   Bemerkung: ς2 = I (I-Identität).

e) Gk,n: Mit Gk,n bezeichnet wir die Gruppe
   von Abbildungen, die durch die Menge der k-Funktion erzeugt wird.

f) DES-like functions:
   Sie f : Vn → Vn, (X,Y) ∈Vn2

   (X,Y)δf= (Y,Xf(Y))

   heißt DES-like function.
   Bemerkung: δf kann auch wie folgt dargestellt
   werden: δf = ςf • Ө, wobei

   (X,Y)Ө= (Y,X),
   (X,Y)ςf= (Xf(Y),Y).

   Es gilt: Ө2 = I, ςf2 = I.

g) DES2n: Mit DES2n bezeichnen wir die
   Gruppe von Abbildungen, die durch die Menge der DES-like functions
   erzeugt wird.

h) 2-restricted DES-like function
   Sei z ∈ Vn. Seien i,j1,j2 drei paar-
   weise verschiedene natürlich Zahlen
   aus 1,n. Sie g : V2 → V1.
   Sie f : Vn → Vn eine Funktion folgender Gestalt

   f(z) = (0, …,0,g(zj1,j2),0, …,0).
         |--⇓--|     i    |--⇓--|
           i-1              n-i

   Dann heißt δ 2-restricted DES-like function.

   wie folgt definiert:

   wobei (i,j) ∈ 1,2n.
   (Vertauschung der Bit i und j).

I.2. Resultate von EVEN, GOLDREICH für den DES

Lemma 1: ∀n > 1: Ө ist eine gerade Permutation.

Lemma 2: ∀n > 1, ∀f: Vn → Vn:
   ςf ist nie eine gerade Permutation.

Beweis: siehe Artikel von EVEN, GOLDREICH.

Folgerung 1: ∀n > 1, ∀f: Vn → Vn:
   δf ist eine gerade Permutation.

Folgerung 2: DES2n C AV2n  (I)

Lemma 3: ∀ i∈1,n ∀ j ∈ n+1,2n:
   ςi,hex kann als eine Folge von 2 restricted DES-like
   functions dargestellt werden.

Lemma 4: ∀ >1: Jede 2-Funktion auf V2n kann als eine Folge
   von 2-restricted DES-like functions dargestellt werden.

Beweis: siehe Artikel.

Forderung 3: ∀n1: Die Gruppe der Permutationen, die
   durch die 2-restricted DES-like functions erzeugt wird,
   fällt mit G2,2n zusammen.
   Da die Menge der 2-restricted DES-like functions eine
   Untermenge der DES-like functions ist, folgt

Forderung 4: G2,2n C DES2n  (II)

Satz 1: (COPPERSMITH, GROSSMAN)
   ∀n≥4, 2 ≤k≤n-2:Gk,n=AVn.  (III)

Beweis: siehe Artikel von COPPERSMITH, GROSSMAN
   Aus (I), (II) und (III) folgt das gesuchte Resultat.

Satz 2: ∀n>1: DES2n = AV2n

I.3.   Resultate für LAMBDA1

I.3.1. Bezeichnungen/Definitionen

a) hc1 c2-Funktion
   Sie∀(x,y,c1,c2) ∈ V⁴n die Funktion
   hc1,c2 wie folgt definiert:

   (x,y)hc1c2= (xc1,yc2).

b) LAMBDA-like functions
   Sei δf eine DES-like function.
   Sie (c1,c2) ∈Vn2.
   Mit LAMBDA-like functions bezeichnen wir die Funktionen

   γfc1,c2= δf o hc1,c2, d. h.
   (x,y)γfc1,c2= (yc1(xf(y))c2).

c) LAMBDA2n:
   Mit LAMBDA2n bezeichnen wir die Gruppe von
   Abbildungen, die durch die Menge der LAMBDA-like functions
   erzeugt wird.

I.3.2. Resultate

Lemma 5: ∀(c1,c2)∈Vn2, ∀n>1:
   hc1,c2 ist eine gerade Permutation.

Beweis:
   Wir stellen hc1,c2 als Hinteranderausfüllung
   vor vier Permutationen dar:

   hc1,c2 = hc1 o Ө o hc2 o Ө, wobei
   (x,y)hc1 = (xc1,y).

   Nach Lemma 1 ist Ө für alle n>1 eine gerade Permutation.
   Die Abbildung hc1 ist aber ebenfalls eine gerade
   Permutation (siehe Anhang, Lemma I für

   f(x) = xhc1,c2 = const)

Folgerung 5: ∀f:Vn → Vn, ∀(c1,c2)∈Vn2:
   γfc1,c2 ist eine gerade Permutation.

Folgerung 6: LAMBDA2n C AV2n.  (IV)

   Andererseits gilt: Die Menge aller DES-like functions
   ist eine Untermenge der Menge aller LAMBDA-like functions.
   Für c1,c2 ≡ 0 fallen beide
   Mengen zusammen.

Folglich: DES2n C LAMBDA2n.  (V)

Vermittels Satz 2, (IC) und (V) erhalten wir das Hauptresultat

Satz 3: ∀n>1: LAMBDA2n = AV2n

IV. Untersuchungen zu schwachen und Semischwachen Schlüsseln für LAMBDA1

IV.1. Allgemeine Bezeichnungen

Sei B=: (B(1), …,B(256)) ∈ V256 der verwendete Schlüssel.
Daraus werden folgende Vektoren (Rundenschlüssel) gebildet:

K1=: (B(1), …B(48)) ∈ V48,
K2=: (B(49), …B(96)) ∈ V48,
K3=: (B(97), …B(144)) ∈ V48,
K4=: (B(145), …B(192)) ∈ V48,
∀j ∈ 5,12: Kj=: T11(Kj-4),
∀j ∈ 13,16: Kj=: T11(K25-j),
K17=: (B(193), …B(224)) ∈ V32,
K18=: (B(225), …B(256)) ∈ V32.

Mit E(B,X) bezeichnen wir die Chiffrierabbildung LAMBDA1
mit den Schlüssel B für den Klartextvektor X ∈ V64.
Analog sei D(B,X) die entsprechende Dechiffrierabbildung.

Laut def. soll X = D(B,E(B,X)) gelten (1)
Für gegebene (L0, R0) ∈ V322 wird die
Chiffrierabbildung E(B,(L0,R0) wie folgt definiert:

(L16,R16) =: E(B,(L0,R0)),
∀j ∈1,16: (Lj,Rj) ∈ V322,

∀j ∈ 1,16:	{	(Lj,Rj) =: (Rj-1,Lj-1G(Rj-1,Kj)), j ∈ {8,16},
		(L8,R8) =: (R7K17,(L7G(R7,K8))K18),
		(L16,R16) =: (L15G(R15,K16),R15).

Für gegebene (L′0,R′0)∈V322 wird die Dechiffrierabbildung

D(B,(L′0,R′0)) wie folgt definiert:
(L′6,R′16) =: D(B,(L′0,R′0)),

∀j ∈ 1,16:	{	(L′j,R′j) =: (R′j-1,L′j-1G(R′j-1,K2j)), j ∈ {8,16},
		(L′8,R′8) =: (R′7K′17,(L′7G(R′7,K′8))K′18),
		(L′16,R′16) =: (L′15G(R′15,K′16),R′15).

Dabei sei ∀j1,16: K′j = K17-j,
     K′17 = OK18,
     K′18 = OK17.

G sei eine Abbildung: G:V32X V48 → V32.

Setzen wir (L′0,R′0) = (L16,R16), ist dann in der Tat(1) erfüllt.
Wir führen weiter noch folgende Bezeichnungen ein:

Sei 0n(0,..,0) ∈ Vn der Nullvektor und
1n = (1, …,1) ∈ Vn der Einsvektor aus dem Vektorraum Vn.

IV.2. Schwache Schlüssel

Definition 1:

Ein Schlüssel B heißt schwacher Schlüssel, genau dann,
wenn ∀X ∈ V64: D(B,X) = E(B,X).

Folgerung 1:
Für einen schwachen Schlüssel B gilt:

∀X ∈ V64: E(B,E(B,X)) = X.

Beweis:
Sei X ∈ V64, beliebig, aber fixiert.

Sei g = E(B,X), laut Definition: X = D(B,g).

Wegen D(B,X) = E(B,X), ∀ X ∈ V64,
folgt dann:

∀ X ∈ V64: X = D(B,g) = E(B,g) = E(B,E(B,X)).

Satz 1:
Sei B derart, daß

′∀i ∈1,16: Ki=K17-i, und K17K18: = 032.

Dann ist B ein schwacher Schlüssel.

Beweis: Offensichtlich ∀i ∈ 1,16: Ki=K17-i=K′17-i.
⇒ ∀i ∈1,16: Ki=K′i und K′=032K18, K′18=032K17.
Sei (L0,R0) = (L′0,R′0)∈V322, beliebig.
Dann gilt laut Definition:

(L1,R1) = (R0,L0G(R0,K1)) = (R′0,L′0G(R′0,K′1)) = (L′1,R′1)
⋅
⋅
⋅
(L7,R7) = (R6,L7G(R6,K7)) = (R′6,L′6G(R′6,K′7)) = (L′7,R′7)
(L8,R8) = (R6K17,(L7G(R7,K8))K18) = (R7K18,(L7G(R7,K8))K17) =
   = (R′7K′17,(L′7G(R′7,K′8))K′18) = (L′8,R′8)
⋅
⋅
⋅
(L16,R16) = (L15G(R15K16),R15) = (L′15G(R′15,K′16),R′15) = (L′16,R′16).

Da (L0,R0) ∈ V322 beliebig gewählt werden kann, folgt sofort
∀X ∈ V64: D(B,X) = E(B,X) und damit die Behauptung des Satzes.

Definition 2: Alle schwachen Schlüssel B ∈ V256,  die den Be-
dingungen von Satz 1 genügen, nennen wir schwache Schlüssel
mit palindromischer Struktur.

Satz 2: Es gibt genau 234 schwache Schlüssel mit
palindromischer Struktur

Beweis: Wir betrachten zunächst die Bedingung
∀i ∈1,16: Ki=K17-i.
Mit den Formeln für die Schlüsselgenerierung erhalten wir

       K1 = K16 = T33K1
       K2 = K15 = T33K2
       K3 = K14 = T33K3
       K4 = K13 = T33K4
T11K1 = K5 = K12 = T22K4
T11K2 = K6 = K11 = T22K3
T11K3 = K7 = K10 = T22K2
T11K4 = K8 = K9  = T22K1
T22K1 = K9 = K8  = T22K4
T22K2 = K10 = K7 = T22K3
T22K3 = K11 = K6 = T22K2
T22K4 = K12 = K5 = T22K1
T33K4 = K13 = K4
T33K3 = K14 = K3
T33K2 = K15 = K2
T33K1 = K16 = K1.

Wie man leicht sieht, sind die letzten acht Gleichungen identisch
zu den ersten acht. Aus letzteren erhalten wir:

a) K1 = T33K1  e) T11K1 = T22K4
b) K2 = T33K2  f) T11K2 = T22K3
c) K3 = T33K3  g) T11K3 = T22K2
d) K4 = T33K4  h) T11K4 = T22K1.

Aus e) und h) folgt sofort: (Man beachte: T⁴⁸ = I)

Andererseits

Analoge Gleichungen erhält man vermittels f) und g)
auch für K2, K3.
Unter Beachtung von a) - d) folgt daraus die notwendige
Bedingung:

∀i ∈1,4: Ki = T22Ki = T33Ki
⇒ ∀i ∈ 1,4: Ki = T11Ki
⇒ ∀i ∈ 1,4: Ki = 048 oder
              Ki = 148.

Unter Beachtung von e) - h) folgen dann genau vier Möglich-
keiten für die Wahl von K1, …,K4:

Sei nun K17 ∈ V32 beliebig, aber fest.
Aus der Bedingung K17K18 = 0, folgt
dann sofort der Wert für K18.
Damit gibt es genau 232 Möglichkeiten für die Wahl von
K17 und K18.
Damit erhalten wir genau 4 ⋅ 232 = 234 schwache
Schlüssel mit Palindromstruktur.

Frage: Gibt es auch schwache Schlüssel mit komplizierter Struktur?


IV.3. Semischwache Schlüssel

Definition 3: Ein Schlüssel B heißt semischwacher Schlüssel,
genau dann wenn

J B * ∈ V256, so daß
∀X ∈ V64: D(B,X) = E(B*,X).

Folgerung 2: Sei B ein semischwacher Schlüssel.
Dann gilt ∀X ∈ V64:

1) D(B*,X) = E(B,X)
   (d. h. B* ist ebenfalls ein semischwacher Schlüssel.)
2) X = E(B*,E(B,X)).

Beweis:

1) Es gilt ∀X ∈ V64: E(B*,X) = D(B,X)
⇒ ∀X ∈ V64 X = D(B*,E(B*,X)) = D(B*,D(B,X)).
   Andererseits
⇒ ∀X ∈ V64 X = E(B,D(B,X)) = E(B,E(B*,X)).
⇒ ∀X ∈ V64 D(B*,D(B,X)) = E(B,E(B*,X)).
  Sei g = D(B,X) = E(B*,X).

Aufgrund der Eineindeutigkeit der Chiffrenabbildungen
folgt dann:

∀g ∈ V64: D(B*,g) = E(B,g).

2) Sei ∀X ∈ V64: D(B*,X) = E(B,X).
⇒ ∀X ∈ V64: X = E(B*,D(B*,X)) = E(B*,E(B,X)).

Satz 3: Seien (B,B*) ∈ V642 derart, daß

   ∀i ∈ 1,16: Ki = K*17-i
   und K17 = 032K*18,
       K18 = 032K*17,

Dann sind B und B* semischwache Schlüssel.

Beweis: Der Beweis verläuft analog dem Beweis von Satz 1.
Offensichtlich gilt ∀i ∈ 1,16:

   Ki = K′17-i = K*′17-i = K*i,

und

   K17 = 032K*18 = K*′17,
   K18 = 032K*17 = K*′18.

Sei nun (L0,R0) = (L*′0,R*′0) ∈ V322 beliebig.
Dann gilt laut Definition

(L1,R1) = (R0,L0G(R0,K1)) =
   = (R*′0,L*′0G(R*′0,K*′1)) = (L*′1,R*′1).
⋅
⋅
⋅
(L7,R7) = (R6,L6G(R6,K7)) =
   = (R*′6,L*′6G(R*′6,K*′7)) = (L*′7,R*′7).
(L8,R8) = (R7K17,(L7,K8))K18) =
   = (R*′7K*′17,(L*′7G(R*′7,K*′8))K*′18)
   = (L*′8,R*′8)
⋅
⋅
⋅
(L16,R16) = (L15G(R15,K15),R15) =
   = (L*′15G(R*′15,K*′16)R*′15) =L*′16,R*′16).

Da (L0,R0) ∈ V322 beliebig gewählt wurden kann,
folgt sofort ∀X ∈ V64: D(B*,X) = E(B,X)
und damit die Behauptung des Satzes.

Definition 4: Alle semischwachen Schlüssel B ∈ V256,
die den Bedingungen von Satz 3 genügen, nennen wir semischwache
Schlüssel mit Palindromstruktur.

Satz 4: Es gibt genau 2⁶⁸ semischwache Schlüssel
mit Palindromstruktur.

Beweis: Wir betrachten zunächst die Bedingung

∀ i ∈1,16: Ki = K*17-i.

Mittels der Formel für die Schlüsselgenerierung erhalten wir:

       K1 = K*16 = T33K*1
       K2 = K*15 = T33K*2
       K3 = K*14 = T33K*3
       K4 = K*13 = T33K*4
T11K1 = K5 = K*12 = T22K*4
T11K2 = K6 = K*11 = T22K*3
T11K3 = K7 = K*10 = T22K*2
T11K4 = K8 = K*9  = T22K*1
T22K1 = K9 = K*8  = T22K*4
T22K2 = K10 = K*7 = T22K*3
T22K3 = K11 = K*6 = T22K*2
T22K4 = K12 = K*5 = T22K*1
T33K4 = K13 = K*4
T33K3 = K14 = K*3
T33K2 = K15 = K*2
T33K1 = K16 = K*1.

Diese Gleichungen fassen wir wie folgt zusammen:

a) K1 = T33K*1 ∧ T33K1 = K*1,
b) K2 = T33K*2 ∧ T33K2 = K*2,
c) K3 = T33K*3 ∧ T33K3 = K*3,
d) K4 = T33K*4 ∧ T33K4 = K*4,
e) T11K1 = T22K*4 ∧ T22K1 = T11K*4,
f) T11K2 = T22K*3 ∧ T22K2 = T11K*3,
g) T11K3 = T22K*2 ∧ T22K3 = T11K*2,
h) T11K4 = T22K*1 ∧ T22K4 = T11K*1.

Vermittels a) und e) erhalten wir

Unter Beachtung von T⁶⁶ = T18 erfolgt
K1 = T18K1 = T22K1.

Auf analoge Art und Weise erhält man:

∀i ∈1,4: Ki = T18Ki = T22Ki  (2)
und K*i = T18K*i = T22Ki.

Durch Vergleich der entsprechenden Schlüsselbits erhält man,
daß (2) nur genau für die vier Vektoren

 048 = (0, …,0) ∈ V48,
0148 = (0,1,0,1, …,0,1,0,1) ∈ V48
1048 = (1,0,1,0, …,1,0,1,0) ∈ V48
 148 = (1, …,1) ∈ V48

erfüllt ist, d. h.

∀i ∈1,4: Ki  = 048 ∨ Ki  = 1048 ∨ Ki  = 1048 ∨ Ki  = 148,
          K*i = 048 ∨ K*i = 1048 ∨ K*i = 1048 ∨ K*i = 148.

Aus a), d) und h) erhält man weiter

K1 = T33K*1 = T22K4 = T⁷K*4.

Analog

K2 = T33K*2 = T22K3 = T⁷K*3.

Daraus erhalten wir für die Wahl von K1, K*1, K4, K*4
lediglich folgende vier Möglichkeiten:

Eine analoge Tabelle erhält man für die Wahl von K2, K*2, K3, K*4.
Damit gibt es genau 16=2⁴ Möglichkeiten für die Wahl von

 Ki, K*i,i ∈1,4.

Wählt am nun (K17 K18) ∈ V322 beliebig,
aber fest, dann erhält man vermittels

K*18 = 032K17 und K*17 = 032K18

sofort die Werte für K*17 und K*18.

Damit gibt es also genau 22⋅232⋅232⋅ = 268
verschiedene Möglichkeiten für semischwache Schlüssel mit Palindromstruktur.

Frage: Gibt es auch semischwache Schlüssel komplizierter Struktur?

Abteilung 2                                    Berlin, 22, Juni 1990
Referat 21

Sachbestandsbericht LAMBDA1

1. Gegentand des Berichtes

Anfang März 1990 ergab sich die dringende Notwendigkeit, umgehend
einen neuen Chiffrieralgorithmus hoher Sicherheit bereitzustellen.
Die Übergabe des Algorithmus für die technische Realisierung er-
folgte bereits am 12. 3. 1990 /3/. Um das Einsatzrisiko möglichst
gering zu halten, eine gründliche und umfassende Analyse war nicht
möglich, erfolgte der Rückgriff auf bewährte Grundstrukturen
(Feistelchiffren).

Eine modifizierte Version des amerikanischen Data Encryption
Standard DES /1/ erschien aus verschiedenen Gründen für den
vorgesehenen Einsatz in den Geräten T316 und T325 geeignet. Die
vorgenommenen Modifizierungen erfolgte mit dem Ziel, die aus der
offenen Literatur und durch eigene Untersuchungen bekannten bzw.
vermuteten Schwachstellen des DES zu vermeiden. Der Bericht be-
inhaltet die wesentlichsten, seit März, erzielten Analyseergeb-
nisse zu der mit LAMBDA1 bezeichneten modifizierten DES-Version.

2. Der LAMBDA1 Algorithmus

LAMBDA1 kann in standardisierten Arbeitsmodi für 64-Bit Block-
chiffrieralgorithmen gemäß ISO 8372 /2/ eingesetzt werden. Die
exakte Beschreibung des Algorithmus findet man in /3/. Im Ver-
gleich zum DES wird
- die effektive Schlüssellänge von 56 auf 256 Bit vergrößert,
- der als Schwäche bzw. als trapdoor vermutete Zusammenhang
  zwischen S-Boxen und Schlüsselfolgeerzeugung ist aufgehoben,
- nach 8 Verarbeitungszyklen (Runden) wird ein Schlüsselvektor
  mit einer Länge von 64 Bit im Algorithmus verarbeitet, um
  analytische Zusammenhänge entscheidend zu verändern,
- die Anfangs- und Endpermutationen IP bzw. IP-1 wurden im Interes-
  se einer effektiven Implementierung geändert.

3. Methodik der Untersuchungen

Die im nachhinein durchzuführende kryptologische Analyse verläuft
in 2 Phasen:
In der ersten Phase erfolgen auf der Basis der ausgewerteten
Veröffentlichungen zur DES-Analyse, analoge Untersuchungen zu
LAMBDA1 (ca. 70 Quellen).

Dazu wurde die vorhandene Literaturübersicht zur Analyse von
Blockchiffren (insbesondere zum DES) vervollständigt und zielge-
richtet ausgewertet.

Tiefergehende Arbeiten sind in der zweiten Phase als Parallelun-
tersuchungen zu den Analysearbeiten für die Algorithmen der DELTA-
Klasse /4/ vorgesehen.

4. Eingesetzte Kräfte/Kapazitäten

Mitte März begann die kryptologische Analyse. An ihr sind 9
Diplommathematiker beteiligt. Wobei alle Mitarbeiter nur ca. 30 %
ihrer Arbeitszeit für diese Arbeiten verwenden.

Für experimentelle Untersuchungen stehen ESER PC und ein AT zur
Verfügung.

Diese Untersuchungen sind unter den gegebenen Bedingungen sehr
aufwendig.

Für einen Versuch benötigt man auf dem ESER PC ca. 10 Stunden.
Auf dem zur Verfügung stehenden AT, der unter heutigen Bedingungen
als Einsteiger-Hardware einzustufen ist, werden pro Versuch nur
ca. 2 Stunden benötigt.

Die Programme laufen hauptsächlich auf ESER PC. Die insgesamt
bisher verbrauchte Rechenzeit beträgt ca. 400 Stunden. Die
Nutzung der Rechner in einer Nachtschicht trägt zwar zur Entspan-
nung der Situation bei, ist aber unter Berücksichtigung der oben
aufgeführten Zeitrelationen unbefriedigend.

Mit durchaus handelsüblicher schneller 16-Bit Technik lägen die
Zeiten bei etwa 10 - 15 Minuten. Somit erweist sich die Lei-
stungsfähigkeit der zur Verfügung stehenden Rechner als ein ent-
scheidender Engpaß, der sich generell hemmend für die Analyse
(auch im Rahmen der DELTA-Analyse) auswirkt. Die rechentech-
nichen Kapazitäten der Abteilung 2 sind durch die Programmierar-
beiten am Chiffrierverfahren KRAKE und die mathematisch-kryptolo-
gische Analyse überfordert.

5. Ergebnisse

5.1. In Anlehnung an die in /5/ untersuchten DES-like functions,
     ergaben Untersuchungen der Gruppe der LAMBDA1-like func-
     tions, daß auch hier die alternierende Gruppe vorliegt.
5.2. Alle schwachen und semischwachen Schlüssel mit Palindrom-
     charakter /6/ wurden eindeutig bestimmt. In Relation zum
     Schlüsselumfang von 22⁵⁶ ist ihr Auftreten jedoch um Größen-
     ordnungen geringer als beim DES.
5.3. Automorphismen
     Es wurden Aussagen bewiesen, die die Anzahl und die Art der
     Automorphismen in einem grundlegenden Automatenmodell
     wesentlich einschränken. Damit sind mehrere Klassen
     kryptologisch evtl. verwendbarer algebraischer Strukturen
     ausgeschlossen.
5.4. Zweifache Transitivität
     Die zweifache Transitivität ist eine wesentliche
     algebraische Eigenschaft für Gruppen von Abbildungen, die in
     Blockchiffren verwendet werden. Die Überprüfung dieser
     Eigenschaft ist auch für die Analyse von LAMBDA1 von Inter-
     esse. Die theoretischen Grundlagen für eine rechnerge-
     stützte Prüfung wurden ausgearbeitet.
5.5. In der Literatur gibt es eine Reihe verschiedener
     statistischer Untersuchungen, mit denen versucht wird, uner-
     wünschte Gesetzmäßigkeiten im Chiffrieralgorithmus zu
     entdecken. /7/
     Geplant und zum Teil begonnen wurden Experimente zum Ava-
     lanche-Effekt und zum strikten Avalanch-Effekt und der Te-
     stung spezieller Bitabhängigkeiten. Aufgrund der geringen
     Leistungsfähigkeit der zur Verfügung stehenden Rechner,
     konnte bisher nur wenige Versuche durchgeführt werden, eine
     endgültige Wertung ist z. Zt. nicht möglich. Die bisherigen
     Versuche zeigen jedoch keine Auffälligkeiten.

6. Wertungen

Alle Aussagen/Wertungen sind durch die sehr kurze Zeit für die
Analysearbeiten zu relativieren. In der Regel sind für solche
komplizierten Arbeiten mindestens 2 Jahre vorzusehen. - Mit dem
Einsatz ist nach wie vor ein gewisses Risiko verbunden. Daraus
ergibt sich die Notwendigkeit, die Analyse weiterzuführen.

6.1. Es wurden bisher keine kryptologisch schlechten Eigenschaften
     gefunden.
6.2. Man kann davon ausgehen, daß praktisch nutzbare Schwachstel-
     len, falls sie existieren, nur mit großem Aufwand auffind-
     bar sind.
6.3. Mit den durchgeführten bzw. noch vorgesehenen Analysearbei-
     ten wird das Niveau der in der offenen Literatur dargelegten
     Analyseergebnisse zum DES erreicht. Arbeiten zu Automorphis-
     men und zur 2-fachen Transitivität gehen darüber hinaus.
6.4. Alle bisherigen Analyseergebnisse unterstützen die These,
     daß der LAMBDA1 Algorithmus nicht schlechter als der DES ist.

7. Schlußfolgerungen

7.1. In Übereinstimmung mit dem in /3/ enthaltenen Vorschlag
     gibt es aus heutiger Sicht keine Einwände für den bis I/91
     begrenzten Einsatz von LAMBDA1 in Datenchiffriertechnik bis
     zum Geheimhaltungsgrad GVS.
7.2. Für das III. Quartal 1990 sind folgende Arbeiten geplant:
     + Prüfung, ob weitere Aussagen aus der offenen Literatur auf
       LAMBDA1 übertragbar sind.
     + die Weiterführung der begonnen Experimente zum Ava-
       lanche-Effekt.
     + Arbeiten zum Nachweis der 2-fachen Transitivität der Grup-
       pe des Automaten und darauf aufbauend der Nachweis, daß
       die alternierende Gruppe erzeugt wird.
     + Suche nach möglichen Automorphismen.
7.3. Die Analyse ist langfristig parallel zur Entwicklung des
     neuen Blockchiffrieralgorithmus weiterzuführen. Ergebnisse
     sind zum Termin I/91 in einem Dokument zusammenzufassen und
     zu werten.
7.4. Es ist durch die hierfür verantwortlichen Mitarbeiter der
     Verwaltung zu prüfen, ob für die vorgesehenen Experimente
     (auch und insbesondere zur Algorithmenklasse DELTA) lei-
     stungsfähigere Rechentechnik (z. B. AT mit 80386 Prozessor)
     zur Verfügung gestellt und die angespannte Situation bzgl.
     der rechentechnischen Kapazität in der Abteilung 2 entspannt
     werden kann.

     In diesem Zusammenhang möchte ich auf unser Schreiben
     vom 08. 05. 1990, zu benötigter Hardware, hinweisen.

Quellen

/1/ Federal Inforamtion Processing Standard (FIPS) Publication
    No. 46, January 1977
    Data Encryption Standard
/2/ International Stndard ISO 8372
    1987 - 08 - 15
    Information processing - Modes of operation for a 64-bit block
    cipher algorithm
/3/ Schreiben Leiter Abt. 2 vom 12. 3. 1990
    Vorlage eines Datenchiffrieralgorithmus
    (Anlage)
/4/ Vorläufige Beschreibung der Chiffrieralgorithmusklasse DELTA
/5/ Even S., Goldreich O.
    DES-like function can generate the alternating group - IEEE Trans.
    Inf. Theory, 1983, Vol. IT-29, No. 6, pp. 863-865
/6/ Simmons G. J., Moore J. H.
    Cycle Structure of the DES for keys having palindromic (or anti-
    palindromic) sequences of rounds keys. - IEEE Trans. Software
    Eng., 1987, Vol. SE-13, No. 2, pp. 262-273
/7/ A. K. Leung, S.E. Tavares
    Sequence complexity as a test for cryptographic systems

     Abteilung 2                             Berlin, 28. April 1990
     Leiter


     Stand der Entwicklungsarbeiten DELTA
     (Anmerkung: Im Rahmen der Entwicklungsarbeiten erwies es sich als
                 arbeitsmethodisch günstig, eine Chiffrieralgorithmus-
                 klasse zu definieren.
                 Um Verwechselungen auszuschließen, erhielt sie die
                 Bezeichnung DELTA. Deshalb erfolgt die Weiterführung
                 der Arbeiten zu LAMBDA 2 unter der Bezeichnung DELTA.)

     Ziel der Entwicklung ist es, eines 64-Bit Blockchiffrieralgo-
     rithmus gemäß ISO 8372 zu entwickeln, der für Staatsgeheimnisse
     einsetzbar ist. Die Strukturierung sollte zu einem schnellen
     Algorithmus für 16-Bit Prozessoren führen.

     Ergebnisse:

     1. Mit einer „Vorläufigen Beschreibung der Chiffrieralgorithmus-
        klasse DELTA“ ist der Rahmen für die weitere Entwicklung und
        Analyse des Algorithmus vorerst abgesteckt.

     2. Eine Analysekonzeption wurde erarbeitet. Die geplante Aufga-
        ben werden voraussichtlich die Hauptkapazität von Ref. 21
        mindestens für das Jahr 1990 binden.

     3. Die Analysearbeiten werden ständig präzisiert, Ergebnisse
        finden in der Entwicklung des Algorithmus bzw. in der Festle-
        gung seiner Parameter ihren Niederschlag.

     4. Analytische Untersuchungen, z.B. zur Gruppeneigenschaft der
        Chiffrierabbildung, sind angelaufen, erste Ergebnisse liegen
        vor.

     5. Erste Programme für experimentelle Untersuchungen wurden erar-
        beitet. Sie werden vorerst zur Analyse von LAMBDA 1 einge-
        setzt, danach zur Analysen von Algorithmusversionen aus DELTA.

     Probleme:

     1. Eine möglichst verbindliche Aussage über die beabsichtigten
        Einsatzbedingungen (Hardware, Software, Zeitforderungen für
        die Chiffrierung) ist erforderlich. Sie könnte die Konstruk-
        tion des Chiffrieralgorithmus beeinflussen.

     Weiter Unterstützungshandlungen und Koordinierungen zum Thema
     sind vorerst nicht absehbar.


                                                 Killmann
                                                 Major d. VP

Referat 21                                  Berlin, 10.4.90



     Vorläufige Beschreibung der Chiffrieralgorithmusklasse
                         D E L T A

     1. Einleitung

     Die im Punkt 2 definierte CA Klasse kann in den standardisierten
     Arbeitsmoden für 64-Bit Blockchiffrieralgorithmen gemäß ISO
     8372 angewandt werden.
     Die Strukturierung soll zu einem schnellen Algorithmus für 16-
     Bit Prozessoren führen und gleichzeitig bei richtiger Anwendung
     die notwendige Sicherheit bieten.
     Bezeichnungen sind für alle kryptanalytischen Arbeiten im
     Referat verbindlich.
     Die Beschreibung ist nicht vollständig, sie will aber zur
     Standardisierung und somit zur Effektivität der Arbeit
     beitragen. Im Zuge der Entwicklungs- und Analysearbeiten erfolgen
     weitere Präzisierungen. Änderungen sind möglich.
     Die Beschreibung der Arbeitsweisen im CBC und CFB Modus erfolgen
     später.

     2. Definitionen

     2.1. Bezeichnungen

     i,j,k,t  Indizes,  T ∈ N

     ∀ m ∈ N:  Vm =: {0,1}m

     R1,R2,R3,R4 Register zu je 16 Bit

     ∀(i,t) ∈ 1,4 x 0,T

       ai(t) ∈ V16                            Inhalt des Registers Ri
                                              zum Zeitpunkt (Takt) t

        i       i      16                            i
       a(t) = (a  (t) V = 1                   wobei a  (t) ∈ {0,1}
                j      j                             j

       Im weitern gilt k ∈ {1,2,3}           beliebig, aber fest.

       Sei X(t) ∈ Vk*16

                          k*16
           X(t) = (x  (t))      ),            wobei x (t) ∈ {0,1}
                    j     j=4                        j


     2.2. Die Abbildung ΦK

         ΦK:  V16 x V16 x V16 x VK*16  --> V16

     (ΦK wird ggf präzisiert. Die Abbildung sollte sich aus
     Operationen zusammengesetzt, die schnell EDV mäßig verarbeitbar
     sind. Z. B.

	Addition mod 216
	Addition mod 216 - 1
	bitweise Addition mod 2 (blockweise)
∧	bitweise and (blockweise)
rot	zyklische Verschiebung links oder rechts
P	Permutation V16 --> V16
	Negation

     2.3.   Beschreibung einer Runde der Arbeitsweise des
            Blockchiffrieralgorithmus


     Abbildung D:   V64   x   VK*16   -->   V64

           ∀ t ∈ 0,T-1 :

            (a1(t+1),a2(t+1),a3(t+2),a⁴(t+1)) = D((a1(t),a2(t),a3(t),a⁴(t)), X(t))

            wobei gilt a1(t+1) = a2(t)

                       a2(t+1) = a3(t)

                       a3(t+1) = a⁴(t)

                       a⁴(t+1) = a1(t)  ΦK((a2(t),a3(t),a⁴(t),  X(t))

            Abbildung D-1  :      V64 x VK*16     --> .V64

           ∀ t ∈ 0,T-1 :

            (a1(t),a2(t), a3(t),a⁴(t)) = D-1(a1(t+1),a2(t+1),a3(t+1),a⁴(t+1)), X(t))

            wobei gilt: a1(t) = a⁴(t+1)  ΦK(a1(t+1),a2(t+1),a3(t+1),X(t))

                        a2(t) = a1(t+1)

                        a3(t) = a2(t+1)

                        a⁴(t) = a3(t+1)

Skizze:


   ┌---  R1 ←---  R2  ←--- R3 ←--- R4  ←------┐
   |              ↓        ↓       ↓          |
   |             \------------------/ ←X      |
   |              \                /          |
   |               \      ΦK      /           |
   |                \            /            |
   |                 \          /             |
   |                  \        /              |
   |                   \      /               |
   |                    \    /                |
   |                     \  /                 |
   |                      \/                  |
   |                       ↓                  |
   └--------------------→  -----------------┘


   2.4 Anzahl der Schlüsselelemente und Anzahl der Runden


   Es wird vorerst auf eine Schlüssellänge von 256 Bit auf 32
   Runden orientiert.

   Sollten Algorithmen dieser Klasse auf der Ebene unterhalb von
   Staatsgeheimnissen eingesetzt werden, dann sind z. B. auch 128
   Bit Schlüssellänge und 16 Runden denkbar.

   In der Abb. Φ sollte ein hinreichend großer LZS wirken.


   3. Bezeichnungen für die Analyse

   3.1. MEDWEDJEV-Automat A = Ak(Par.,n)

   Par.-Bezeichnung für den variablen Parameter, der durch die
        Wahl eines LZS fixiert wird.

                          n
         Eingabenmenge  V
                          K*16

         Zustandsmenge  V64

                                   n
         Überführungsfunktion:  Δ V   x   V64  --> V64
                                   k*16

                n      n                           n
        ∀ (X(t))    ∈ V        ∀ a ∈ V      δ((X(t)     ) Dn (X(1),X(2), … X(n))a
                t=1    k*16           64           t=1


         partielle Überführungsfunktion:

                n      n
        ∀ (X(t))    ∈ V         ∀ a ∈ V64 δx(1),x(2), …X(n)     a=: Dn(X(1),X(2), … X(n))a
                t=1    k*16

         wobei Dn(X(1),X(2), … ,X(n)) a=: D(X(n),D(X(n-1), … D(X(1),a) …))


         Gruppe des Automaten
                                                                  n
         GA  =: < { δ(X(1),X(2), … X(n) | { X(1),X(2), … X(n) ∈ V   } >
                                                                  k*16



          Anlage 1
          Varianten für den DELTA-Algorithmus
          (gleichzeitig Beschreibung des ECB Modus)

          Sei a der Klartextblock mit 64 bit und c der Geheimtextblock
          mit 64 bit d.h. a ∈ V64, c ∈ V64


         Variante DELTA 1\1

         n = 64

         S ∈ V256

         S = ( s1 , …, s256   ),    wobei∀ i ∈ 1,256 : si ∈ (0,1)

         t ∈ 1,16 : X(t) = (s(t-1)16+1          , …,s(t-1)16+16  )

         t ∈ 17,64 : X(t) = rot(7R) X(t-16)

         Φ1 (a2(t), a3(t), a⁴(t), X(t) =: rot (3L) P{[a2(t)  a3(t) ]  [a⁴(t)  X(t)]}


         Die Chiffrierabbildung:

         c =: D⁶⁴ [X(1),X(2), …,X(64)] a

         Die Dechiffrierabbildung:

         a =: D-64 [X(64),X(63, …;X(2)] c


         Variante DELTA 1\2

         n = 64

         S ∈ V2⁵⁶

         S = (s1 , …,s256   ), wobei ∀ i ∈ 1,256 : si ∈ {0,1}

         t ∈ 1,16 : X(t) = (s(t-1)16+1   , …,s(t-1)16+16 )

         t ∈ 17,64 : X(t) = rot(7R) X(t-16)

         Π - Permutation der 4  16-bit Blöcke:

         Π (a1(t),a2(t), a3(t),a⁴(t)) =: a⁴(t),a3(t),a2(t),a1(t)

         Φ1 (a2(t), a3(t),a⁴(t), X(t)) =: rot(3L) P{[a2(t)  a⁴(t)]  [a3(t)  X(t)]}


         Die Chiffrierabbildung:

         c =: Π {D⁶⁴[X(1),X(2), …,X(64)]a}

         Die Dechiffrierabbildung:

         a =: Π {D⁶⁴[X(64),X(63), …,X(1))]c}


         Varianten für den DELTA-Algorithmus
         (gleichzeitig Beschreibung des ECB-Modus)

         Sei a der Klartextblock mit 64 Bit und c der Geheimtextblock
         mit 64 Bit, d. h. a ∈ V64  , c ∈ V64



        Variante DELTA 2\1

        n = 32,

        s ∈ V256

        S = (s1 , … , s256    ), wobei ∀ i ∈ 1,256 : si ∈ {0,1}

       t ∈ 1,8 : X(t) = (s (t-1)*32+1             , … , s(t-1)*32+32 )

       t ∈ 9,32 : X(t) = ROR7 X(t-8)

       t ∈ 1,32 : x1(t) = ((X1(t)) , … , (X16(t)) )

                 x2(t) = ((X17(t))  , … , (X32(t)) )

       Φ2 (a2(t), a3(t), a⁴(t), X(t)) =: P {[a2(t)  a⁴(t)  X1(t) ]  (ROR3 [a3(t)  x2(t) ] ) }


       Die Chiffrierabbildung:

       c =: D32 [X(1), X(2), … , X(32)] a


       Die Dechiffrierabbildung:

       a =: D-32 [X(32), X(31), … , X(1)] c


       Variante DELTA 2\2

       n = 32,

       S ∈ V256

       S = (s1 , …, s256   ),     wobei ∀ i ∈ 1,256 : si ∈ {0,1}

       t ∈ 1,8 : X(t) = (s(t-1)*32+1 , … , s(t-1)*32+32 )

       t ∈ 9,32 : X(t) = ROR7 X(t-8)

       t ∈ 1,32 : X1(t) = ((X(t))1 , … , (X(t))16 )

                  X2(t) = ((X(t))17 , … , (X(t))32 )

       Π - Permutation der 4 16-Bit Blöcke

       Π (a1(t), a2(t), a3(t), a⁴(t)) =: (a⁴(t), a3(t), a2(t), x1(t)]}

       Φ2 (a2(t), a3(t), a⁴(t), X(t)) =: P {[a2(t)  a⁴(t)  X1(t)]  (ROR3 [a3(t)  X2(t) ] ) }


      Die Chiffrierabbildung:

       c =: Π (D32 [X(1), X(2), … , X(32)] a)


     Die Dechiffrierabbildung:

      a =: Π (D32 [X(32, X(31), … , X(1)] c)


      Anlage 2

      Die Arbeitswiese im CBC/CFB Modus und Imitationsschutz.
      (Anmerkung: Durch die Beschreibung der Varianten des DELTA Algo-
                  rithmus in Anlage 1 ist die Arbeitsweise im ECB Modus
                  vollständig beschrieben.)

      1. Die Arbeitsweise im CBC Modus ist mit der Beschreibung in ISO
         8372 vollständig identisch.

      2. Die Arbeitsweise im CFB Modus ist mit der Beschreibung in ISO
         8372 vollständig identisch.

      3. Für den OFD Modus wird folgendes festgelegt:
                                      32
         A(∅), B(∅), E, F, ∈ V32  ;    Add. mod. 232
                                      32
                                        Add. mod. 232 - 1

         A(∅), B(∅) werden aus einem Startvektor SY (SyF) von 64 Bit
                    gebildet

         E, F seien Konstanten (ungerade)

         Erzeugt werden die Folgen A(j), B(j), j ∈ 1,m , m ∈ N;
                                                   32
                                   A(j) =: A(j-1)    E
                                                   32
                                   B(j) =: B(j-1)    F

         Weiterhin sei:

         ∀ j ∈ 1,m: a(j) = (A(j), B(j))

         Die Additionsreihe C(j) j ∈ 1,m ergibt sich durch Anwendung
         des Chiffrieralgorithmus (im ECB Modus auf die Folge

         a(j) j ∈ 1,m.

         (Die Konstanten E, F sind noch zu präzisieren.)

         4. - Durch Anwendung des CBC Modus ist ein gewisser Imitations-
              schutz gegeben.

            - Falls eine offene Übertragung oder Speicherung der Daten
              vorgesehen ist, bietet die Speicherung bzw. Übertragung nur
              des letzten 64-Bit Vektors des im CBC Modus chiffrierten
              gesamten Textes einen Imitationsschutz. (Ob für diese
              Version eine Reduzierung der Rundenzahl in der Arbeit des
              Chiffrieralgorithmus vorgenommen werden kann, bleibt zu
              Untersuchen.)

            - Die Einbindung einer Imitationsschutzvariante für den Algo-
              rithmus muß weiter untersucht und präzisiert werden.


            E := 000 1 000 000 1 000 000 1 000 000 1
            P := 000 000 01 0001 0001 0001 0001 0001 0001

     Referat 21                               Berlin, 29.5.90


     Ergänzung zur Anlage 2, Punkt 3.
     Vorläufige Variante für E und F

     E =: (0001 0000 0010 0000 0100 0000 1000 0001)
     F =: (0000 0001 0001 0001 0001 0001 0001 0001)

     Version DELTA 1\1

        a1(t) --- a2(t) --- a3(t) --- a⁴(t)
         |         |         |         |
         |         └---------        --- X(t)
         |                   |         |
         |                   └-------┘
         |                        |
         |                        P
         |                        |
         └------------------------
                                  |
                                 a⁴(t+1)


     Version DELTA 1\2

      a1(t) --- a2(t) --- a3(t) --- a⁴(t)
       |          |        |         |
       |          └----------------┘
       |             |     |
       |             └-----
       |                   |
       |                   P
       |                   |
       └-------------------
                           |
                          a⁴(t)


     Version DELTA 2\1

          a1(t)    a2(t)   a3(t)    a⁴(t)
           |        |       |        |
           |        └----------------
           |                |        |
           |                |        -- X1(t)
           |                |        |
           |                ----------- X2(t)
           |                |        |
           |              ROR 3      |
           |                |        |
           |                -------┘
           |                |
           |                P
           |                |
           └----------------
                            |
                            a⁴(t)


     Version DELTA 2\2

         a1(t)       a2(t)     a3(t)    a⁴(t)
          |           |         |        |
          |           └------------------
          |                     |        |
          |                     |        - X1(t)
          |                     |        |
          |                     ---------- X2(t)
          |                     |        |
          |                   ROR 3      |
          |                     |        |
          |                     -------┘
          |                     |
          |                     P
          |                     |
          └---------------------
                                |
                                a⁴(t)

    Abschätzen Laufzeiten                         12.7.1990

    Anlage   Programm       Korn   Δ 1\1          44 Befehle
                                   Δ 1\2          44
                                   Δ 2\1          60
                                   Δ 2\2          60

    Vergleich                      R (9,6 Kbit)   96
                                 DES (9,6 Kbit)   85
                                   R (reine       ~200
                                     Software)
                                 DES (reine       ~200
                                     Software)


     gesicherte Aussage für alle Variante DELTA!
     Doppelt so schnell wie die reine Softwarelösung DES
     (z.Z. 12 ms ohne xxx)

          2     <=   6 ms    (f = 2,5 MHz, Z80)

     32 Umläufe
         Δ 1      schneller Δ 2
         Δ 1      <= 5 - 5,2 ms

     16 Umläufe für Δ 2
               ~ 3ms            4 x so schnell wie DES, reine Softwarelösung


     Programmversion Korn Δ1\1 Entwurf, ungetestet)
                          6L. SYF   - Synchronfolge
                          6L. KEY   - Schlüssel
                          6L. Perm1 - Permutation1
                              Perm2

     Ausgangspunkt:

        A     - UMLZ
       BC     - a⁴(t)
       DE     - a3(t)
       HL     - a2(t)
       IX     - a1(t)

       Stack:

       a2 (t)
       a1 (t)
       a3 (t)
       a4 (t)
       UMLZ

       M:   PUSH AF      ; UMLZ (Umlaufzähler)
            PUSH BC      ; a4 (t)
            PUSH DE      ; a3 (t)
            PUSH IX      ; a2 (t)
            PUSH HL      ; a1 (t)
                                            ┐
            LD A,D       ; a2 (t)           |            (-)
            CPL          ; (-)              |
            ADD H        ;                 > a2(t)  a3(t)
            LD D,A                          |
            LD A,E                          |
            CPL                             |
            ADC L                           |
            LD E,A                          ┘

            LD HL, 6L.KEY                   ┐
            LD A,B                          |
            ADD H                           |
            LD B,A                           > a⁴(t)  X(t)
            INC HL                          |
            LD A,C                          |
            ADC H                           ┘
            XOR E         ;  a3(t)
            LD C,A
            LD A,B
            XOR D
            LD B,A        ;  a3(t) Ergebnis in BC

            LD H,6L.PERM1  ; Permutation 4 Bit Adresse
            LD L, B        ;          -> 4 Bit Deth.
            LD B, H
            LD H,6L.PERM2
            LD L,C
            LD C,H

            POP IX
            POP DE         ; a2(t)               a⁴(t) -> a3(t) -> a2(t) -> a1(t)

            LD A,B
            XOR D          ; a1(t)  Ergebnis PERM
            LD B,A
            LD A,C
            XOR E
            LD C,A         ; in BC     neuer Wert a⁴(t+1)
            POP HL         ; alt a⁴(t)            a2(t+1)
            POP DE         ; alt a⁴(t) neuer Wert a3(t+1)
            POP AF
            DEC A
            JRNZ M∅-#



     Versuchsalgorithmus V2  (32 Runden)


     Datin (64 Bit)                     Schl (256 Bit)
     1 ……  8                      1 2 ………… 16
          |                                       |
     -------------                      --------------------------
     ↓   ↓   ↓   ↓                      ↓   ↓   ↓  ↓  ↓   ↓  ↓   ↓
     a1  a2  a3  a4                      x1  x2  s21 s22 s31 s32 s41 s42
     |   ↓   |   ↓                      /    |
     |   Neg |    ←--------------------Zahl/
     |   |   |   ↓                    /
     |   |   |   F3                  /
     |   |   ↓   |                  /
     |   └-→  ←------------------/
     |       ↓   |
     |      F2   |
     |       |   |
     |       →  ←
     |         ↓        LZS
     |       K-Box ←--- 1 …… 128
     |         |
     |         |<------ Rotation
     |         |
     └-------→ 
               ↓
            Permut
  <-------     ↓ 
  D2 D3 D4    |_|