DEC Design Frage (SHA3)

[TurboMagic]

Hallo,

so wie es scheint, bekomme ich den SHA3 langsam in den Griff.
Ich habe mal SHA3 224 durch Umbau von Wolfgang Erhard's (WE) Code
"roh" umgesetzt (siehe Entwicklungszweig) und mit einem Konsolenprogramm
mit dem offiziellen NIST 200 Byte Testvektor mal grundsätzlich getestet.

Nur habe ich da ein paar Fragestellungen:

1. Der ganze SHA3 Code basiert immer auf Bit als Größenangabe statt Byte.
Ich habe es mittels Schleife jetzt so umgesetzt, dass er immer max.
BufferSize an Daten berechnet, damit auch große Datenmengen möglich sind.
Gegenüber WE's Code kann das leichte Performanceverluste ergeben, da
mehr Funktionsaufrufe als bei ihm nötig auftreten können. Es geht dabei
um den Absorb Aufruf.
Die Alternative wäre, bis zu einer maximalen Datengröße die in Bit in
das Größenfeld des Absorbs passt diesen direkt aufzurufen und dann für
den evtl. vorhandenen Rest nochmal. Wie muss ich eine Prüfung ob die zu
bearbeitende Datengröße * 8 ohne Überlauf in den entsprechenden Parameter
des Absorb Aufrufes passt?

2. Der SHA3 Algorithmus hat als besonderheit im Vergleich zu anderen
Hash-Algorithmen die Eigenschaft, dass auch unvollständige Bytes verarbeiten
können. Also das Bilden eines Hashes über nur 5 Bit oder über 9 Bit ist
möglich. Nur passt das bisher nicht zur Architektur der DEC.
Wie müsste sowas angeboten werden?
Als eigentsändige Methoden in der SHA3 Basisklasse?
Und für welche Datentypen sollte das sinnvollerweise umgesetzt werden?
Diese "Sondervarianten" wären dann halt nicht in den vorhandenen Interfaces
drin oder für andere Methoden wie KDF etc. verfügbar, das ist aber vermutlich
verschmerzbar, da Hashes für solche nicht in ganzen Bytes dimensionierten
Datengrößen sicher nicht so oft benötigt werden. Oder?

Wenn das so passt, was ich da umgesetzt habe sollte wohl in absehbarer Zeit
eine neue Version mit SHA3 Unterstützung verfügbar sein.

Grüße
TurboMagic

[Michael II]

Du solltest deine Arbeit unbedingt hier anmelden und verlinken lassen:

https://keccak.team/software.html

(Falls du nicht bereit drauf bist, unter anderem Namen ;-))

[TurboMagic]

Hallo,

danke für den Tipp. Dazu muss es aber noch vollends reifen.
Und das war ja meine hauptsächliche Fragestellung: wie mit
diesen Bit Größenangaben sinnvoll umgehen?

Grüße
TurboMagic

[TurboMagic]

Hier eine meiner Fragestellungen präzisiert.
Wie muss man folgenden Code ändern, damit nicht immer nur BlockSize
an Daten in einem Schritt verarbeitet werden, sondern soviel wie möglich
aber ohne, dass dieses * 8 zur Umrechnung in Bit zu einer verminderung
der maximal insgesammt möglichen Datengröße führt?

DataSize ist übrigens ein Integer (ja man müsste mal untersuchen ob man das
problemfrei auf UInt32 oder UInt64 ändern kann, aber die Methodensignatur
nutzen auch alle anderen Hash Algorithmen der DEC).

Delphi-Quellcode:

while (UInt32(DataSize) >= BlockSize) do
begin
  Absorb(Pointer(@Data), BlockSize * 8);
  Dec(DataSize, BlockSize);
end;

Grüße
TurboMagic

[himitsu]

BlockSize erhöhen?

Ich denke mal das ist grade dafür da, um den gleichzeitig verwendeten Speicher zu begrenzen/partitionieren?

Gibt es nach der Schleife noch eine Behandlung für den "Rest"? (kleiner als Blocksize)

Delphi-Quellcode:

if UInt32(DataSize) >= BlockSize then  // falls Absorb bei Size=0 nicht abraucht, dann könnte man das IF auch weglassen
begin
  Absorb(Pointer(@Data), (UInt32(DataSize) div BlockSize * BlockSize) * 8);  // wenn BlockSize immer eine 2er-Potenz ist, dann könnte man auch einfach eine Bitmaske drüberegen/ANDen)
  DataSize = {Int32}(UInt32(DataSize) mod BlockSize);  // DateSize-Typ? um keinen eventuellen Überlaufcheck-Code vom Compiler reinzubekommen
end;

[TurboMagic]

Ja nach der Schleife gibt's noch einen Aufruf für den Rest.
Sonst wäre für alle Situationen wo's einen Rest gibt das
Ergebnis falsch.

Man könnte die Blocksize erhöhen ja, aber das wäre ja auch
wieder statisch und ich bin mir auch nicht mehr sicher, woher
ich die aktuell benutzten Werte für die Blocksize(s) der
SHA3 Varianten habe. Ich habe mir damals (musste das leider
immer wieder liegen lassen) hoffentlich was dabei gedacht...

Ich hatte mirn eigentlich einen allgemeinen Lösungsansatz
erhofft, bin mir nur halt nicht sicher wie ich mit dieser
Begrenzung durch die Basierung der Datengröße auf Bits statt
Byte umgehen müsste...

Grüße
TurboMagic

[Michael II]

Hallo TM

kannst du mal anhand eines konkreten Beispiels
- Länge Zustandsvektor
- Länge Hash
- Blockgrösse bei Absorption
erläutern, was du tust?

Durch die "Länge" des verwendeten Zustandsvektors und die Länge des Hashs ist die Blockgrösse bei jedem Absorptionsschritt ja eigentlich vorgegeben - und du hast damit keinen Spielraum, wie viele Bits des Zustandsvektors bzw. der Nachricht je Absorptionsschritt verwendet werden dürfen.

Oder anders geschrieben: Falls deine absorb() Funktion genau einen Absorptionsschritt erledigt, dann ist der zweite Parameter nicht frei wählbar.

Zitat:

Ich habe es mittels Schleife jetzt so umgesetzt, dass er immer max.
BufferSize an Daten berechnet, damit auch große Datenmengen möglich sind.

Ich kenne eure Codes nicht. Da aber sowohl der Zustandsvektor wie auch der Hash feste (von der Länge der Nachricht unabhängige) Grösse haben, sehe ich nicht, wo bei der Absorption ein Problem entsteht, wenn eine lange Nachricht verarbeitet werden muss. War es im ursprünglichen Code schlicht nicht vorgesehen/möglich?
(Delphi technisch: Da SHA3 die Nachricht Block nach Block absorbiert, wäre in einigen Anwendungsfällen (zum Beispiel bei grossen Nachrichten) die Verwendung eines Streams ok(?))


Deine Frage 2 ist - wenn ich dich richtig verstehe - Delphi technischer Natur und nicht SHA3 Mathe.
Punkto Mathe hast du ja bereits alles. Da Nachrichtenlänge mod Blocklänge selten 0 ist, musst du auch bereits bei deiner Byte basierten Lösung meistens den letzten zu verarbeitenden Nachrichtenblock auffüllen (10..01 Padding). Das ist Bit basiert genau gleich.

[TurboMagic]

Hallo,

was ich tue ist im Development (und seit eben auch im Master) Branch dieses
Repositories zu finden:

https://github.com/MHumm/DelphiEncryptionCompendium

Als Beispiel kann der Unit Test mit dem originalen 1600 Bit NIST Testvektor
von A3 dienen. Beim SHA3-224 habe ich als Blockgröße 144 Byte drin, womit die
200 Byte des Testvektors größer wären als die Blockgröße.

Meine Schleife funktioniert in sofern, dass als Ergebnis auch der vom NIST
publizierte raus kommt.

So wie der ursprüngliche Code von W. Erhardt geschrieben war, musste man ja immer
die länge der zu verarbeitenden Daten in Bit angeben, was bei größeren Datenmengen
evtl. nicht ausgericht hätte, da man dann maximal MaxInt div 8 Byte verarbeiten
könnte.

Richtig?
Ich habe nur in Herrn Erhardts (un den kann man ja leider nicht mehr fragen) Code
nichts gesehen was diese Fälle behandelt hätte, daher die Schleife.

Zu der Stream Idee: die DEC bietet bereits Stream basierte Methoden, aber eben
nicht nur. Und alle Methoden rufen intern die Calc Methode auf, in welcher ich jetzt
die Schleife umgesetzt habe.

Hier ein etwas einfacheres Testprogramm als die Unit Tests:

Delphi-Quellcode:

program Hash_Console;

{$APPTYPE CONSOLE}

{$R *.res}

uses
  System.SysUtils,
  DECFormat,
  DECHash;

var
  s  : RawByteString;
  WE : THash_SHA3_224;
begin
  WE := THash_SHA3_224.Create;
  try
    WriteLn('SHA3 224 Test');
    s := '';

    for var i := 1 to 200 do
      s := s + #$A3;

    s := WE.CalcString(s, TFormat_HexL);
    WriteLn(s);
  finally
    WE.Free;
  end;

  ReadLn;
end.

Korrektes Ergebnis (NIST) ist dieses:
9376816aba503f72f96ce7eb65ac095deee3be4bf9bbc2a1cb 7e11e0

Grüße
TurboMagic

[Michael II]

Das wollte ich eigentlich zuerst schreiben: Wenn's funktioniert, dann ist es ja sicher auch richtig ;-).

Deinen Code muss ich dann mal laden, wenn...

Du verarbeitest bei SHA3-224 bei einer Wortlänge von 2^6 im Zustandsvektor bei der Absorption jeweils eine Blockgrösse von r = 25*2^6 - 2*224 = 1600 - 2*224 = 1152 Bit, dies entspricht deinen 144 Byte. Also ok.

Dann nehme ich an, dass Blocksize in deinem Code in #4 in Byte abgespeichert ist (in deinem SHA3-224 Fall also 144) und deine Absorption absorb() (wie erwartet und sinnvoll) genau einen Absorptionsschritt durchführt, und der zweite Parameter deiner absobrb() Funktion die Blockgrösse in Bit (also hier 1152) erwartet (deshalb dein *8).

Du fragst in #4

Zitat:

Wie muss man folgenden Code ändern, damit nicht immer nur BlockSize
an Daten in einem Schritt verarbeitet werden, sondern soviel wie möglich

Geht nicht. Lass es so wie es ist. "Blocksize an Daten" ist genau soviel wie geht. Remember: SHA3 arbeitet die Nachrichtenblöcke nacheinander in deinen Zustandsvektor ein.

Besten Dank für deine Arbeit!

Gruss und viel Spass,
Michael

[TurboMagic]

Danke für deine Bestätigung!
Das hilft mir mental sehr!

Im übrigen scheinst du gute Kryptographiekenntnisse
zu haben!

Grüße
TurboMagic

[Michael II]

Hallo TM

ich habe in der vergangenen Nacht deine DEC geladen, getestet und dann gesehen, dass in deiner Schleife der Data-Pointer nicht angepasst wird. absorb() liest deshalb immer die ersten Bytes der Nachricht und liefert falsche Resultate (ausser bei N=xxxxxxxxx.xxxxxxxxx, x=0..255)

Bei deinem Test mit der Nachricht for var i := 1 to 200 do s := s + #$A3; fällt das Problem nicht auf, da absorb() immer nur #$A3 liest. Dein absorb() in der Schleife las halt bei jedem Durchlauf die ersten Bytes anstatt korrekt der Reihe nach irgendwann alle.

So sollte es funktionieren (Code unten). Du oder irgendwer hier im Forum können das sicher schöner schreiben ;-). V.a. aber nicht nur Englischer und so...

Ich habe hier unten im Code eine Variable prorunde eingebaut. Das war nur zum Testen der Funktionsweise von absorb(N,x). (Ein Kontentheoretiker hat uns mal während einer Woche besucht und jene mathematische Probleme aufgezählt, für welche 17 die Lösung ist. Wenn man also mal nicht weiter weiss, dann ist 17....;-)).
absorb(N,x) ist so geschrieben, dass du für prorunde irgend einen positiven Wert <= maxint div 8 wählen kannst. Ein hoher Wert macht natürlich Sinn.

Delphi-Quellcode:

procedure THash_SHA3Base.Calc(const Data; DataSize: Integer);
var prorunde, absorb_byte : integer;
    gelesen : integer;
    p : PByte;

begin
  // due to the way the inherited calc is constructed it must not be called here!
  if (DataSize > 0) then
  begin
    p := Pointer(@Data);
    gelesen := 0;
    prorunde := 17;
    while ( DataSize > 0 ) do
    begin
      absorb_byte := DataSize;
      if absorb_byte > prorunde then absorb_byte := prorunde;
      Absorb( @p[gelesen], absorb_byte*8);
      inc( gelesen, absorb_byte );
      dec( DataSize, absorb_byte );
    end;
  end
  else
    FinalStep;
end;

Ich habe die Funktion getestet mit drei SHA3-224 Onlinerechnern; scheint OK zu sein.

[himitsu]

Zitat:

Delphi-Quellcode:

      absorb_bytes := DataSize;
      if absorb_bytes > prorunde then absorb_bytes := prorunde;

Also mathematisch ein

Delphi-Quellcode:

      absorb_bytes := Min(DataSize, {prorunde}BlockSize);

:stupid:

Zitat:

Delphi-Quellcode:

for var i := 1 to 200 do
      s := s + #$A3;

Joar, für den Test wäre es bestimmt besser, hier nicht mit dem Selben, sondern mit unterschiedlichen/gemischten Zeichen zu arbeiten. (

Delphi-Quellcode:

s := s + Char(i + 35);

)
Aber nur um die Schleife zu ersetzen, DupeString, StringOfChar oder string.Create (TStringHelper.Create).

[Michael II]

Zitat:

Zitat von himitsu (Beitrag 1489427)

Zitat:

Delphi-Quellcode:

      absorb_bytes := DataSize;
      if absorb_bytes > prorunde then absorb_bytes := prorunde;

Also mathematisch ein

Delphi-Quellcode:

      absorb_bytes := Min(DataSize, {prorunde}BlockSize);

:stupid:

Genau.

Es ist und war mir voll bewusst, dass man eine min Funktion schreiben könnte (hatte ich sogar während dem Testen). Oder in DECHash die Unit Math einbinden kann. Ich bin kein Fan, von Funktionsaufrufen, wo's keine braucht. Wer hier mit Lesbarkeit argumentiert, muss sich eine Hirnbrille kaufen. Also besten Dank für deinen grandiosen Hinweis ;-).

Blocksize (dein Code). Geht zwar auch (prorunde ist in [1 bis maxint div 8] frei wählbar, BlockSize hingegen ist in DECHash definiert und eine feste Grösse abhängig vom verwendeten Zustandsvektor (5 Worte zu l Bit (hier 6)) und von n (hier 224)).
Wenn du dir function THash_SHA3Base.Absorb(Data: Pointer; DatabitLen: Int32): Int32; anschaust ist BlockSize im Gegensatz zu meiner früheren Behauptung (als ich den Code noch nicht kannte) nicht Wert der Wahl.

[himitsu]

Keine Sorge, das ist eine Inline-Funktion, also der Compiler sollte den Aufruf entfernen.

System.Math.pas bindet auch kaum Code ein, außer einem SSE-Test und der SysUtils,
aber für die ordentliche Fehlerbehandlung sollte die SysUtils ja eh schon drin sein.

[Michael II]

Jo... besten Dank. Ich deklariere - wenn ich auch mal kurze Hilfsfunktionen schreibe ;-) - auch inline, wo's sinnvoll ist.

Einen sonnigen Tag wünsche ich uns allen.

[TurboMagic]

Zitat:

Zitat von himitsu (Beitrag 1489427)

Zitat:

Delphi-Quellcode:

for var i := 1 to 200 do
      s := s + #$A3;

Joar, für den Test wäre es bestimmt besser, hier nicht mit dem Selben, sondern mit unterschiedlichen/gemischten Zeichen zu arbeiten. (

Delphi-Quellcode:

s := s + Char(i + 35);

)

Sag' das Mal dem NIST, die haben diesen dusseligen Testvektor
so definiert...

Grüße
TurboMagic

[himitsu]

Na das ist ja blöd. So bekommt man doch nicht mit, wenn man irgendwo 'nen Offset falsch/vergessen hat. :shock:

[Michael II]

Nur für himitsu ;-).

Delphi-Quellcode:

function min(const a,b : integer):integer;inline;
begin
  if a<b then Result := a else Result := b;
end;

procedure THash_SHA3Base.Calc(const Data; DataSize: Integer);
var prorunde, absorbiere_bytes : integer;
    gelesen : integer;
    p : PByte;

begin
  // due to the way the inherited calc is constructed it must not be called here!
  if (DataSize > 0) then
  begin
    p := Pointer(@Data);
    gelesen := 0;
    prorunde := maxint div 8;
    while ( gelesen < DataSize ) do
    begin
      absorbiere_bytes := min( DataSize-gelesen, prorunde );
      Absorb( @p[gelesen], absorbiere_bytes*8);
      inc( gelesen, absorbiere_bytes );
    end;
  end
  else
    FinalStep;
end;

[TurboMagic]

Zitat:

Zitat von himitsu (Beitrag 1489440)

Na das ist ja blöd. So bekommt man doch nicht mit, wenn man irgendwo 'nen Offset falsch/vergessen hat. :shock:

Ich sag' ja, du sollst denen Sagen, dass Sie Mist publizieren.
Alle Testvektoren (zumindest die für 1600 Bit, die anderen aber
glaube ich auch) aller SHA3 Varianten sind so von denen publiziert.

Ach ja, die neue SHA3 Umsetzung hat lt. Michael noch einen Bug.
Der schlägt nur unter gewissen Randbedingungen zu.
Den beseitige ich später.

"Dieser Bug tritt auf, wenn für die Länge t der Nachricht N gilt
t mod MaxRoundSize liegt in [1...BlockSize-1]."

Falls jemand einen Testvektor zur Hand hat würde ich den in die
Unittests einbauen.

Grüße
TurboMagic

[Michael II]

Mein Testvektor.

Delphi-Quellcode:

var
  s : RawByteString;
...
   for var i := 1 to 10 do
      s := s + 'e21et2e2et1208e7t12e07812te08127et1028e7t1208e7gd81d872t178r02tr370823';
   s := s + 'TurboMagic';
// Rechnen
    writeln( s = 'f7fc914c8fe4827d866b02df2459840260f4adb0db4deb9fa661756c' );

Diese Seiten könnten helfen, falls jemand hilft beim Überprüfen deiner DEC:
https://emn178.github.io/online-tools/sha3_224.html
https://md5calc.com/hash
https://codebeautify.org/sha3-224-hash-generator


Am besten holst du dir eines der unter #2 gelinkten Pakete:
https://keccak.team/software.html

Dann kannst du automatisiert Hashes erzeugen und mit deiner DEC gegenchecken lassen.

[TurboMagic]

Seltsam.
Habe den Code jetzt korrigiert, die bisherigen Unittests laufen auch sauber durch.
Sieht jetzt so aus:

Delphi-Quellcode:

procedure THash_SHA3Base.Calc(const Data; DataSize: Integer);
var
  DataPtr   : PByte;
  RoundSize : UInt32;
const
  // Maximum number of bytes one can process in one round
  MaxRoundSize = MaxInt div 8;
begin
  // due to the way the inherited calc is constructed it must not be called here!
  if (DataSize > 0) then
  begin
    DataPtr := PByte(@Data);

    while (UInt32(DataSize) > 0) do
    begin
      RoundSize := DataSize;
      if (RoundSize > MaxRoundSize) then
        RoundSize := MaxRoundSize;

      Absorb(DataPtr, RoundSize * 8);
      Dec(DataSize, RoundSize);
      Inc(DataPtr, RoundSize);
    end;
  end
  else
    FinalStep;
end;

Nur, dein neuer Testvektor liefert ein anderes Ergebnis als das von dir gepostete.
Hier der AUszug aus der SHA3_224.SetUp Methode mit dem neuen Vektor. Der Wert für
ExpectedOutputUTFStrTest stimmt nicht, solange aber schon für ExpectedOutput was
falsches raus kommt brauche ich den noch nicht anzupassen.

Delphi-Quellcode:

  lDataRow := FTestData.AddRow;
  lDataRow.ExpectedOutput           := 'f7fc914c8fe4827d866b02df2459840260f4adb0db4deb9fa661756c';
  lDataRow.ExpectedOutputUTFStrTest := '0f1ad8cd5a85fe68319b67427e1f0b685498bc246a81a1f595c89e4e';
  lDataRow.AddInputVector(RawByteString('e21et2e2et1208e7t12e07812te08127et1028e7t1208e7gd81d872t178r02tr370823' +
                                        'e21et2e2et1208e7t12e07812te08127et1028e7t1208e7gd81d872t178r02tr370823' +
                                        'e21et2e2et1208e7t12e07812te08127et1028e7t1208e7gd81d872t178r02tr370823' +
                                        'e21et2e2et1208e7t12e07812te08127et1028e7t1208e7gd81d872t178r02tr370823' +
                                        'e21et2e2et1208e7t12e07812te08127et1028e7t1208e7gd81d872t178r02tr370823' +
                                        'e21et2e2et1208e7t12e07812te08127et1028e7t1208e7gd81d872t178r02tr370823' +
                                        'e21et2e2et1208e7t12e07812te08127et1028e7t1208e7gd81d872t178r02tr370823' +
                                        'e21et2e2et1208e7t12e07812te08127et1028e7t1208e7gd81d872t178r02tr370823' +
                                        'e21et2e2et1208e7t12e07812te08127et1028e7t1208e7gd81d872t178r02tr370823' +
                                        'e21et2e2et1208e7t12e07812te08127et1028e7t1208e7gd81d872t178r02tr370823' +
                                        'TurboMagic'));

Meldung von DUnit:
"TestCalcRawByteString: ETestFailure
at $006D7C6D
Index: 3 - expected: <f7fc914c8fe4827d866b02df2459840260f4adb0db4deb9fa 661756c>
but was: <f912f9fcba30ec218d9fc4b682a5ac3457635be038d08a8af 5f44241>"

Was läuft da falsch?

Grüße
TurboMagic

[TurboMagic]

Im Entwicklungszweig ist jetzt übrigens (das Unit Test Problem besteht weiterhin) der Start
einer neuen Zwischenbasisklasse für bitweise Hashes.

[Michael II]

Zitat:

Zitat von TurboMagic (Beitrag 1489467)

Seltsam.
Habe den Code jetzt korrigiert, die bisherigen Unittests laufen auch sauber durch.
Sieht jetzt so aus:

Meldung von DUnit:
"TestCalcRawByteString: ETestFailure
at $006D7C6D
Index: 3 - expected: <f7fc914c8fe4827d866b02df2459840260f4adb0db4deb9fa 661756c>
but was: <f912f9fcba30ec218d9fc4b682a5ac3457635be038d08a8af 5f44241>"

Was läuft da falsch?

Grüße
TurboMagic

Sorry TM..

Du fragst, was falsch läuft... ? Ich laufe falsch. Ich sollte mehr schlafen und weniger posten - oder wenn doch, dann nur vollständigen Code und nicht Auszüge.

Ich habe deine neuste Version gerade jetzt geladen. Auch meine Testnachricht wird von deiner Funktion korrekt "gehasht".
(Ich sehe gerade, dass in der soeben heruntergeladenen DEC von github immer noch die alte procedure THash_SHA3Base.Calc() drin ist. Hab's soeben mit deiner hier geposteten laufen lassen - auch ok.)

Das s := s+s+s ging verloren. So sieht's aus:

Delphi-Quellcode:

uses
  System.SysUtils,
  DECFormat,
  DECHash;

var
  s : RawByteString;
  WE : THash_SHA3_224;
begin
  WE := THash_SHA3_224.Create;
  try
    WriteLn('SHA3 224 Test');
    s := '';

   for var i := 1 to 10 do
      s := s + 'e21et2e2et1208e7t12e07812te08127et1028e7t1208e7gd81d872t178r02tr370823';
   s := s + 'TurboMagic';
   s := s + s + s;

   writeln( length(s).ToString );
   writeln( s );
    s := WE.CalcString(s, TFormat_HexL);
    WriteLn(s);
    writeln( s = 'f7fc914c8fe4827d866b02df2459840260f4adb0db4deb9fa661756c' );
  finally
    WE.Free;
  end;

  ReadLn;

[TurboMagic]

Danke!
Habe das übernommen und jetzt passt das!

Meine Änderungen sind übrigens im Entwicklugnszweig.

und ja: richtig Schlafen hilft oft! ;-)

Grüße
TurboMagic

[Michael II]

Punkto Speed.

Hast du dies hier mal angeschaut:

https://www.delphitools.info/2016/04...tation-kernel/

oder ist es vielleicht bereits eingebaut (?).

[TurboMagic]

Hallo,

1. Ich habe jetzt bis auf einen Unit Test den ich mir noch anschauen muss
(Zeit läuft mal wieder weg) die bitweise Geschichte mal eingebaut.
Man muss dazu FinalBitLength auf die Bitzahl des letzten Byte setzen
und als Größe, falls ein solcher Parameter exisitiert,die Byteanzahl
inkl. des unvollständigen letzten Byte.

2. Zum Thema Geschwindigkeit: darum hab' ich mich noch kein bisschen
gekümmert. Zuerst muss mal die gerade in Arbeit befindliche Integration
funktionieren. Dann können wir zusammen auch das andere angehen.

3. Der bisherigen Integration fehlt auch noch die Umsetzung einiger
weiterer Testvektoren als Unittests. Das kommt schrittweise auch noch.

Grüße
TurboMagic

[Michael II]

Wenn du richtig viel Speed willst, baust du dir eh SHA3-Hardware ;-). [Sehr wahrscheinlich gibt es viel schnellere, als jene, welche man im Netz findet. Falls jemand hier beim BND o.ä. arbeitet: Wie schnell sind eure Lösungen?]

Auf
https://blogs.embarcadero.com/powerf...s-development/

wird
https://github.com/Xor-el/HashLib4Pascal

Ich nehme mal an, dass du das nicht auch bist. Mit diesem Paket könntest du automatisiert Testvektoren durchrechnen lassen und mit deinen Werten vergleichen. (Viele Vektoren musst du ja nicht rechnen lassen.)

Der Download von Herrn Grange (siehe #25 - der mit dem schnellen Absorb) klappte heute nicht, die haben genau heute "maintenance".

Deine aktuelle SHA3 hat mehr Durchsatz als die oben verlinkte.

Die oben verlinkte SHA3_224 Throughput: 34.10 MB/s with Blocks of 64 KB
Deine: 52MB/s

SHA3_256 Throughput: 36.25 MB/s with Blocks of 64 KB
Deine: 52MB/s

SHA3_512 Throughput: 19.98 MB/s with Blocks of 64 KB
Deine: 28MB/s

[himitsu]

DEC selber, das ursprüngliche wurde von "einem" schlauen Typen (negaH / Hagen Reddmann) privat entwickelt, der aber vor ganzen eine Weile mit Delphi aufhörte. :cry:
Und so weit ich weiß, waren seine Implementationen oft die Schnellsten, von einem Privat-Entwickler. (nur ein paar kommerzielle/staatliche professionelle Entwicklergruppen waren teilweise etwas schneller)

[Michael II]

Zitat:

Zitat von himitsu (Beitrag 1489548)

DEC selber, das ursprüngliche wurde von "einem" schlauen Typen privat entwickelt, der aber vor eine Weile verstarb. :cry:
Und so weit ich weiß, waren seine Implementationen oft die Schnellsten, von einem Privat-Entwickler. (nur ein paar kommerzielle/staatliche professionelle Entwicklergruppen waren teilweise etwas schneller)

Ja ich weiss - ich sollte den Urheber* natürlich unbedingt auch erwähnen.
Der Link bei #25 führt zu einer Webseite (*Wolfgang Erhardts DEC wird erwähnt) mit Permutationscode von Eric Grange, welcher offenbar schneller ist als DECHash.THash_SHA3Base.KeccakPermutation(var state: TState_L);

Allgemein und nicht speziell für diesen Code: Kennst du Software, welche einfachen Code wie unter DECHash.THash_SHA3Base.KeccakPermutation(var state: TState_L); automatisch analysiert und punkto Speed optimieren kann? (abhängig von der Hardware-Umgebung, vom möglichen Input,...) Und schreib jetzt nicht Compiler ;-))

[TurboMagic]

Hallo,

1. Der Benchmark bezieht sich auf diese hier, oder?
https://github.com/Xor-el/HashLib4Pascal

2. An der bin ich nicht beteiligt, die enthält aber ein paar Algorithmen (ich rede jetzt nicht
von den nicht kryptographischen) die in DEC noch fehlen. Aber eins nach dem anderen.

3. Der ursprüngliche Autor der DEC war Haagen Redmann. Ist der gestorben?
Der hatte irgendwann einfach kein Interesse mehr daran. Die DEC ging dan auf Assertor
(Frederik Winkelsdorf, Freelancer aber leider nicht mehr im Delphi Umfeld) über und
dann bin ich eingestiegen und habe nauch einiger Zeit der "Betreuung" meines Tuns durch
Frederik die DEC dann ganz übernommen, freue mich aber genre über weitere unterstützer,
da auch meine Zeit und Kenntnisse endlich sind.

4. Der Autor der eingebauten SHA3 Lösung war der tatsächlich gestorbene Wolfgang Erhardt.

So und ich mach mich jetzt an ein paar Formatierungsverbesserungen und in der SHA3Base
sind glaube ich auch noch ein paar Sachen public die eher private/protected sein sollten...

Grüße
TurboMagic

[himitsu]

Zitat:

Wolfgang Erhardts DEC wird erwähnt

Wolfgang hatte auch eine kryptographische Bibliothek,
aber das DEC (Delphi Encryption Compendium) und DECMath waren von Hagen Redmann.

[Michael II]

Zitat:

Zitat von TurboMagic (Beitrag 1489557)

Hallo,

1. Der Benchmark bezieht sich auf diese hier, oder?
https://github.com/Xor-el/HashLib4Pascal

2. An der bin ich nicht beteiligt, die enthält aber ein paar Algorithmen (ich rede jetzt nicht
von den nicht kryptographischen) die in DEC noch fehlen. Aber eins nach dem anderen.

3. Der ursprüngliche Autor der DEC war Haagen Redmann. Ist der gestorben?
Der hatte irgendwann einfach kein Interesse mehr daran. Die DEC ging dan auf Assertor
(Frederik Winkelsdorf, Freelancer aber leider nicht mehr im Delphi Umfeld) über und
dann bin ich eingestiegen und habe nauch einiger Zeit der "Betreuung" meines Tuns durch
Frederik die DEC dann ganz übernommen, freue mich aber genre über weitere unterstützer,
da auch meine Zeit und Kenntnisse endlich sind.

4. Der Autor der eingebauten SHA3 Lösung war der tatsächlich gestorbene Wolfgang Erhardt.

So und ich mach mich jetzt an ein paar Formatierungsverbesserungen und in der SHA3Base
sind glaube ich auch noch ein paar Sachen public die eher private/protected sein sollten...

Grüße
TurboMagic

1. Ja genau. DEC ist schneller auf meinem Uraltnotebook (i7-3632QM CPU).

2. OK. V.a. für heute noch genutzte Dinge interessant und natürlich nur wenn schneller als bei den anderen ;-).

3. Merci. Ich schreibe heute noch 10 Mal von Hand "RTFM".

4. Eric Grange beschreibt wie er ThetaRhoPiChiIota schneller als Wolfgang Erhardt geschafft hat. Das tönt interessant.

[TurboMagic]

Hallo,

hier noch der relevante Auszug aus meiner Anfrage an das NIST wegen der Testdaten die ich dort gefunden hatte:

"Your observation is correct that the example values do not catch some implementation failures. However, this is not their intended purpose: they are sample values, not test vectors.

The goal of the sample values is to make it easy to understand the intermediate values of the algorithm. By choosing a repeating pattern, we can recognize many other repeating patterns in the first few intermediate values of the algorithm. The non-repeating pattern that you propose does not have this property, and may therefore be less suitable as sample to understand the intermediate values.

If test vectors for SHA-3 are needed, they can be found here: https://csrc.nist.gov/Projects/cryptographic-algorithm-validation-program/Secure-Hashing"

Grüße
TurboMagic

[Michael II]

Die Seite Cryptographic Standards and Guidelines ist auch sehr interessant (nicht nur für SHA3). Dort wird für SHA3 (FIPS 202) für einige Testvektoren Runde für Runde die Keccak Permutation (Beispiel) durchgerechnet. Das ist v.a. für Leute sehr brauchbar, welche den schnellsten SHA3 Hash Code programmieren wollen und nicht gleich auf Anhieb den gewünschten Output erhalten.

Wieso NIST derart den Narren gefressen hat an Testvektoren wie 43434343.... ist schwer nachvollziehbar. Sie publizieren aber zum Glück auch (gut sortiert) massenhaft andere.

[Michael II]

Ich habe jetzt noch die in #25 erwähnte Optimierung getestet. Eric Granges optimierter ASM-Code schafft bei SHA3_256 rund 160MB/s. DEC momentan rund 52MB/s.

[ Ganz was anderes, aber auch SHA3... im Netz gibt es viele Webseiten, auf welchen man eigene :stupid: Passwörter eingeben kann, um zu prüfen, wie Hacker sicher diese sind. Man kann auch den SHA3 Hash eines Passwortes eingeben und raus kommt das Passwort, (natürlich) falls in der jeweiligen DB vorhanden. Wenn das Passwort in DB noch nicht vorhanden war, dann sicher bald in der nicht öffentlichen DB2 ;-). ]

[TiGü]

Wie soll denn das gehen?
Wie soll denn aus dem SHA-3 Hash das Passwort zurück gerechnet werden?

[himitsu]

ähnlich wie für MD5?

Da gibt es schon vollständige Rainbowtables, mit jedem existierenden Hash, zu dem "irgendein" Passwort hinterlegt ist. (oder sogar Mehrere)


Du bekommst also nicht "dein" Passwort, sondern Igendeines, welches aber den selben Hash besitzt.

[Rollo62]

Zitat:

Zitat von Michael II (Beitrag 1489667)

Wieso NIST derart den Narren gefressen hat an Testvektoren wie 43434343.... ist schwer nachvollziehbar.

Vielleicht weil viele Leute auch Passwörter wie CCCCCC nutzen :lol:

[TurboMagic]

Zitat:

Zitat von Michael II (Beitrag 1489715)

Ich habe jetzt noch die in #25 erwähnte Optimierung getestet. Eric Granges optimierter ASM-Code schafft bei SHA3_256 rund 160MB/s. DEC momentan rund 52MB/s.

Wie hast du das getestet?
Sein Projekt runtergeladen und ausgeführt?

Ich muss meine SHA3 Arbeiten (da steht noch die Sache mit dem Umstellen des Fehlerhandlings
aus und sicherheitshalber die Integration der besseren NIST Testvektoren) wohl ein paar Tage auf Eis legen.
Jemand hat im SCOOP Algorithmus bugs gefunden, die aber scheinbar nur auf nicht Intel CPUs auftreten...
Scheint ein FPC Benutzer zu sein und hat auf Nachfrage (siehe Issues bei DEC) auch vernünftig reagiert.

Grüße
TurboMagic

[Michael II]

Zitat:

Zitat von TurboMagic (Beitrag 1489776)

Zitat:

Zitat von Michael II (Beitrag 1489715)

Ich habe jetzt noch die in #25 erwähnte Optimierung getestet. Eric Granges optimierter ASM-Code schafft bei SHA3_256 rund 160MB/s. DEC momentan rund 52MB/s.

Wie hast du das getestet?
Sein Projekt runtergeladen und ausgeführt?

Ich muss meine SHA3 Arbeiten (da steht noch die Sache mit dem Umstellen des Fehlerhandlings
aus und sicherheitshalber die Integration der besseren NIST Testvektoren) wohl ein paar Tage auf Eis legen.
Jemand hat im SCOOP Algorithmus bugs gefunden, die aber scheinbar nur auf nicht Intel CPUs auftreten...
Scheint ein FPC Benutzer zu sein und hat auf Nachfrage (siehe Issues bei DEC) auch vernünftig reagiert.

Grüße
TurboMagic

Hallo TM,
ja, ich habe sowohl mit DEC wie mit Grange (über KeccakPermutationKernel in dwsSHA3.pas) viele Male einen RawByteString mit Länge 100 Mio Bytes verarbeiten lassen und die Zeit gemessen. (Uralt Core(TM) i7-3632QM).

Hast du gesehen TM? Rollo62 weiss wieso einfache Textvektoren wie XXXXXX bei NIST sogar Testvektoren sind. Ich wäre selber nie darauf gekommen. Danke Rollo62.:thumb:

Zu TiGü #36: Hashwert -> Passwort geht eben relativ schlecht ;-). Deshalb werden die von in #35 und #37 erwähnten Datenbanken angelegt und genutzt.

Zu #37: Klar... Hash Funktionen sind nicht injektiv: Die Definitionsmenge hat in der Regel mehr Elemente als die Wertemenge. Deshalb könnten in der Tat mehrere Passworte den gleichen Hashwert haben. - Wenn du aber davon ausgehst, dass Passworte eine Länge l mit l<=16 aufweisen und pro Zeichen ca. 100 voneinander verschiedene Werte verwendet werden, dann hast du für l<=16 ~2^106,32 Passworte*, die Menge aller SHA3-256 Werte aber ist mit 2^256 Elementen mächtiger. D.h. es wird maximal (maximal, falls 0 Kollisionen) nur jeder 2^(256-2^106.32)=2^149.68ste Hashwert überhaupt getroffen.
*hier sind alle Summe(100^l (l=1 bis 16)) möglichen Zeichen-Kombinationen berücksichtigt - meistens weisen Passworte Muster auf. Effektiv verwendet wird nur ein sehr kleiner Bruchteil aller möglichen Passworte.

"Brute Force" für einfache Passwörter: Mit "Grange" kann ich auf meinem Core(TM) i7-3632QM pro Sekunde für 1.3 Mio Passworte die SHA3-256 Werte berechnen lassen (Da für alle Passworte mit Länge l<=135Byte in Bit gilt l < r=b-2*n-2=1600-512, wird immer nur genau eine Keccak Permutation durchgeführt). Wenn ich alle Passworte der Form 4'000 mögliche Namen, dann 1 bis 3 stellige Zahl, und abschliessend eines aus 30 möglichen Sonderzeichen durchchecken will, dann sind das 4000*1000*30=120 Mio Passworte. Mit meinem bescheidenen Rechner sind nach zwei Minuten alle solchen Passworte erstellt und alle SHA3 Werte (multithreaded) berechnet. Im Schnitt finde ich mit Grange zu gegebenem SHA3-256 Hash ein solches Passwort (falls es in der Liste der 120 Mio Passwörter vorkommt) also in einer Minute. Grossrechner schaffen mehrere Milliarden SHA3 Werte pro Sekunde.
Spielerei.., ich weiss. Sehr wahrscheinlich kennen aber viele Menschen andere Menschen, welche ziemlich genau diesen Passworttyp verwenden.

Falls sich jemand hier mal mit SHA3 Hashes von kurzen* Vektoren (*Hash nach einer Keccak Permutation berechnet) befasst hat oder ein Paper dazu kennt... das wäre interessant.