Welche Methoden kann ich verwenden, um den 4-Bit-Prüfsummenalgorithmus zu analysieren und zu erraten?

Question

[Hintergrundgeschichte]

Ich arbeite mit einem 5 Jahre alten Benutzeridentifikationssystem und versuche, der Datenbank IDs hinzuzufügen. Das Problem, das ich habe, ist, dass das System, das die ID-Nummern liest, eine Art Prüfsumme benötigt, und niemand, der jetzt hier arbeitet, hat jemals damit gearbeitet, also weiß niemand, wie es funktioniert.

Ich habe Zugriff auf die Liste der vorhandenen IDs, die bereits korrekte Prüfsummen aufweisen. Da die Prüfsumme nur 16 mögliche Werte hat, kann ich jede beliebige ID erstellen und sie bis zu 16 Mal durch das Authentifizierungssystem laufen lassen, bis ich die richtige Prüfsumme erhalte (dies ist jedoch recht zeitaufwändig).

[Frage]

Welche Methoden kann ich verwenden, um den Prüfsummenalgorithmus für bestimmte Daten zu erraten? Ich habe einige einfache Methoden wie XORing und Summierung ausprobiert, aber diese haben nicht funktioniert.

Meine Frage ist also: Wenn ich Daten (in hexadezimaler Form) wie diese habe:

data        checksum
00029921    1
00013481    B
00026001    3
00004541    8

Mit welchen Methoden kann ich herausfinden, welche Art von Prüfsumme verwendet wird? D.h. sollte ich es mit fortlaufenden Nummern wie 00029921,00029922,00029923,... oder 00029911,00029921,00029931,... versuchen? Wenn ich dies tue, nach welchen Mustern sollte ich in der sich ändernden Prüfsumme suchen?

Würde ein Vergleich der vertauschten Ziffern etwas Nützliches über die Prüfsumme aussagen? d.h. 00013481 und 00031481

Gibt es sonst noch etwas, das mir etwas Nützliches sagen könnte? Wie wäre es mit der Invertierung eines Bits oder vielleicht einer Hex-Ziffer?

Ich gehe davon aus, dass es sich um einen gängigen Prüfsummenalgorithmus handelt, aber ich weiß nicht, wo ich mit dem Testen beginnen soll. Ich habe die folgenden Links gelesen, bin mir aber nicht sicher, ob ich irgendetwas davon auf meinen Fall anwenden kann, da ich nicht glaube, dass es sich um einen CRC handelt.

stackoverflow.com/questions/149617/wie-kann-ich-einen-prüfsummen-algorithmus stackoverflow.com/questions/2896753/find-the-algorithm-that-generates-the-checksum cosc.canterbury.ac.nz/greg.ewing/essays/CRC-Reverse-Engineering.html

[ANTWORT]

Ich habe jetzt eine viel größere Liste von Daten heruntergeladen, und es stellte sich heraus, dass es einfacher war, als ich erwartet hatte, aber der Vollständigkeit halber, hier ist, was ich getan habe.

Daten:

00024901 A
00024911 B
00024921 C
00024931 D
00042811 A
00042871 0
00042881 1
00042891 2
00042901 A
00042921 C
00042961 0
00042971 1
00042981 2
00043021 4
00043031 5
00043041 6
00043051 7
00043061 8
00043071 9
00043081 A
00043101 3
00043111 4
00043121 5
00043141 7
00043151 8
00043161 9
00043171 A
00044291 E

Daraus konnte ich ersehen, dass, wenn nur ein Wert um einen Wert erhöht wurde, auch die Prüfsumme um denselben Wert wie in erhöht wurde:

00024901 A
00024911 B

Auch das Vertauschen von zwei Ziffern änderte die Prüfsumme nicht:

00024901 A
00042901 A

Dies bedeutet, dass der Polynomwert (zumindest für diese beiden Positionen) derselbe sein muss

Schließlich war die Prüfsumme für 00000000 A, also habe ich die Summe der Ziffern plus A mod 16 berechnet:
( (x _i ) +0xA )mod16
Und das passte zu allen Werten, die ich hatte. Um sicherzugehen, dass mit den ersten 3 Ziffern, die sich in meinen Daten nie änderten, nichts Schummriges vor sich ging, habe ich mir ein paar Zahlen ausgedacht und getestet, wie Eric vorgeschlagen hatte, und die haben auch alle funktioniert!

Answer 1

Viele Prüfsummen, die ich gesehen habe, verwenden einfache gewichtete Werte auf der Grundlage der Position der Ziffern. Wenn die Gewichte beispielsweise 3, 5, 7 sind, könnte die Prüfsumme 3*c[0] + 5*c[1] + 7*c[2] lauten, und das Ergebnis ist dann mod 10. (In Ihrem Fall mod 16, da Sie eine 4-Bit-Prüfsumme haben)

Um zu prüfen, ob dies der Fall sein könnte, schlage ich vor, dass Sie einige einfache Werte in Ihr System eingeben, um eine Antwort zu erhalten:

1000000 = ?
0100000 = ?
0010000 = ?

... usw. Wenn es einfache Gewichte gibt, die auf der Position basieren, kann dies aufgedeckt werden. Selbst wenn der Algorithmus etwas anderes ist, kann es aufschlussreich sein, schöne, einfache Werte einzugeben und nach Mustern zu suchen. Wie Matti vorschlug, müssen Sie/wir wahrscheinlich mehr Proben sehen, bevor wir das Muster entschlüsseln können.