10-stelliger Barcode, doppelte CRC's und TCP

Chris schrieb:
> Gleich wie es kein CRC bei TCP gibt existiert auch kein CRC im
> Barcode.

Das meinte ich nicht.


Beim 10-stelligen Barcode:

Wie finde ich doppelte CRC's heraus?



Beim TCP:

Checksum über den Header und die Daten oder nur über den Header und die 
Länge der Daten im Header?

1) Brute Force

Andreas V. schrieb:
> Beim 10-stelligen Barcode:
> Wie finde ich doppelte CRC's heraus?

Brute-Force.

Ansonsten "CRC collision" suchen und die Implementierung für die 
Programmiersprache deiner Wahl als Startpunkt nehmen.

Jan H. schrieb:
> 1) Brute Force

Damit hätte ich 2^32 * 2^32 = 18446744073709551616

Schleifendurchläufe!

Ein Hash sprengt alle Speichergrenzen!

test schrieb:
> Aber nicht alle Zahlenkombinationen eines Barcode sind gültig (aus Sicht
> der Anwendung).
>
> Das meint...
>
> Die Wahrscheinlich das ein zufälliger Lesefehler (es geht ja nicht um
> gezielte Manipulation) den Barcode so verändert, das der CRC trotzdem
> gültig ist, ist ja ungleich unwahrscheinlicher (als deine Rechnung
> impliziert).
>
> Und das dieser fehlerhafte Barcode (der aufgrund eines unglaublichen
> Zufall trotzdem durch die CRC Prüfung gekommen ist) auch noch zufällig
> einen gültigen Inhalt hat (also z.B. eine gültige Produktnummer ist, die
> auch in der Datenbank ist) ist dann nochmal um einig unwahrscheinlicher.

Und genau das ist mitunder mein Problem. Ich bekomme aus einer 
Altanwendung (kein Quellcode vorhanden) teilweise (ca. 5%) ungültige 
Barcodes die durch TCP übermittelt wurden und weiß nicht wie sie 
zustandekommen....

test schrieb:
> Was sind das für Barcodes (welches System) und wie ist der
> Barcodeleser
> konfiguriert (Anleitung, evtl. ist die CRC Prüfung deaktiviert? Oder,
> oder, oder...).

Ich habe wie bereits erwähnt einen !0-stelligen Barcode, übermittelt mit 
TCP, CRC aus. Man verlässt sich komplett auf TCP. Keine weiteren 
Prüfmechanismen.

test schrieb:
> Es gibt dutzende unterschiedliche Barcodesysteme.
> Ist es z.B. https://de.m.wikipedia.org/wiki/Code_39 ist dein Problem
> normal (also das Verhalten (was du beobachtest) ist zu erwarten).
> Ist es z.B. https://de.m.wikipedia.org/wiki/Code128 ist entweder der
> Barcodeleser falsch konfiguriert oder du hast ein Software/Netzwerk
> Problem.

Ich gehe von einem (Software/)Netzwerk Problem aus....

Ich tippe auf Reflexionen, EMV bzw. auf ein kaputtes Kabel...

c-hater schrieb:
> Das ist doch ein völlig anderes Problem. Da wird doch ein Fehler
> erkannt.
>
> Bei Kollisionen wird hingegen KEIN Fehler erkannt, obwohl einer da
> ist.
>
> Wenn du nicht einmal diesen Unterschied begriffen hast... Tsss...

Ja, aber der Fehler wird erst vom nachgelagerten CRM erkannt, weil es 
ungültige Barcodes bekommt.
Aber meine Frage war letztendlich: Kann ich mich auf die Daten vom TCP 
verlassen oder nur darauf dass die Länge korrekt war?

Checksum über Header oder Checksum über Header und Daten?

Ich persönlich sende normalerweise immer eine CRC über die Daten mit.

test schrieb:
> Ich verstehe nicht warum du dich so auf TCP festlegst ohne vorher
> erstmal das sehr viel wahrscheinlichere zu prüfen.

Der Barcode an das Steuer-System wird richtig gesendet. Somit ist der 
Barcodeleser vom vorgelagerten System richtig eingestellt.

Wie wird die checksum beim TCP gebildet?  Ich bin mir nicht mehr sicher!

BTW: Meistens habe ich ein System das den Barcode einliest oder 
weitergibt, ein Messsystem und ein Steuersystem.

Wenn beim Steuer-System ein richtiger Barcode ankommt und auf zweitem 
Weg beim Mess-System ein falscher ankommt, dann wurde etwas auf dem Weg 
dorthin verfälscht.


Meine Frage:

Wie wird die checksum beim TCP gebildet?  Ich bin mir nicht mehr sicher!

Checksum über Header oder Checksum über Header und Daten?

Geht die Gesamt-Datenlänge in die Checksum mit ein oder Header + Daten 
selbst?

Hallo,

Andreas V. schrieb:
> Jan H. schrieb:
>> 1) Brute Force
>
> Damit hätte ich 2^32 * 2^32 = 18446744073709551616
>
> Schleifendurchläufe!
>
> Ein Hash sprengt alle Speichergrenzen!

Deine CRCs lassen sich doch s.o. als 32 Bit-Zahlen darstellen?

Das heißt, Deine Tabelle muss eine Größe von 2^32 Bit haben, also gerade 
mal 512 MB, oder?

Und du suchst doch, wenn ich dich recht verstanden habe, die 
Information, wie viele der 9 999 999 999 möglichen Barcodes eine CRC 
doppelt haben, oder? Das sind doch gerade mal 9 999 999 999 
Schleifendurchläufe, oder was übersehe ich da?

CRCs sind doch meist recht zackig berechnet? Liegt das nicht normal so 
bei einigen 100 bis 1000 MB/s auf halbwegs aktuellen Rechnern? Das 
sollte doch kein nennenswertes Problem für einen Desktoprechner sein?

vlg
 Timm

Das ist aber nur die halbe Wahrheit...
Die Checksumme wird aus einem Pseudo Header gebildet.

Da sind mitunder SRC IP und DST IP dabei, die nicht zu TCP, sondern zu 
IP gehören!...

Die Checksum stimmt trotzdem nicht. Das ist jetzt nur für mich.

Es kann natürlich sein dass ich das Padding irgendwo vergass....

Hallo zusammen!

Ich habe mir einfach mal die Mühe gemacht zu recherchieren wie sich die 
Checksum tatsächlich errechnet.
In einem Beispiel sendet der TCP-Server als Antwort die Zeichenfolge 
"ABCD"
vom Rechner 192.168.0.1 (Port 80)
zum Rechner 192.168.0.2 (Port 51941).

Der Pseudo-Header wird in der Methode GetPseudoHeaderFrame() erstellt 
und als ByteArray zurückgegeben.

Die Methoden InternetChecksum und ComputeHeaderIpChecksum sind 
äquivalent.

Damit keiner mehr Lebenszeit damit verschwendet gebe ich meinen Code 
hier weiter:

1

using System;

2

using System.Collections.Generic;

3

using System.Linq;

4

using System.Text;

5

using System.Threading.Tasks;

6

7

namespace CalcTcpCrc

8

{

9

    class Program

10

    {

11

        public static ushort InternetChecksum(byte[] buffer)

12

        {           

13

            int length = buffer.Length;

14

            int i = 0;

15

            UInt32 sum = 0;

16

            UInt32 data = 0;

17

            while (length > 1)

18

            {

19

                data = 0;

20

                data = (UInt32)(

21

                ((UInt32)(buffer[i]) << 8)

22

                |

23

                ((UInt32)(buffer[i + 1]) & 0xFF)

24

                );

25

26

                sum += data;

27

                if ((sum & 0xFFFF0000) > 0)

28

                {

29

                    sum = sum & 0xFFFF;

30

                    sum += 1;

31

                }

32

33

                i += 2;

34

                length -= 2;

35

            }

36

37

            if (length > 0)

38

            {

39

                sum += (UInt32)(buffer[i] << 8);

40

                //sum += (UInt32)(buffer[i]);

41

                if ((sum & 0xFFFF0000) > 0)

42

                {

43

                    sum = sum & 0xFFFF;

44

                    sum += 1;

45

                }

46

            }

47

            sum = ~sum;

48

            sum = sum & 0xFFFF;

49

            return (UInt16)sum;

50

        }

51

52

53

54

        public static ushort ComputeHeaderIpChecksum(byte[] header, int start, int length)

55

        {

56

            ushort word16;

57

            long sum = 0;

58

            for (int i = start; i < (length + start); i += 2)

59

            {

60

                word16 = (ushort)(((header[i] << 8) & 0xFF00) + (header[i + 1] & 0xFF));

61

                sum += (long)word16;

62

            }

63

            while ((sum >> 16) != 0)

64

            {

65

                sum = (sum & 0xFFFF) + (sum >> 16);

66

            }

67

            sum = ~sum;

68

            return (ushort)sum;

69

        }

70

71

72

73

        public static byte[] GetPseudoHeaderFrame()

74

        {

75

            byte[] buffer = new byte[]{

76

                0xc0, 0xa8, 0x00, 0x01,   // SRC-Port 192.168.0.1 (aus IP Header)

77

                0xc0, 0xa8, 0x00, 0x02,   // DST-Port 192.168.0.2 (aus IP Header)

78

                0x00, 0x06, 0x00, 0x18,   // reserved(zeros) | Protocol 6 = TCP | TCPLen = 4(Data) + 20(Header, siehe 0x50) = 24 (0x0018)

79

                0x00, 0x50, 0xca, 0xe5,   // srcPort(80) / dstPort(51941)

80

                0xd1, 0x5b, 0x59, 0x6d,   // SEQNo 

81

                0xbc, 0xb6, 0xcd, 0x8e,   // AckNo

82

                0x50, 0x10, 0x02, 0x0c,   // 5 (4 Bit) = 5 * 4 = 20 Byte Headerlänge | Flags | Window Size = 20c

83

                0x00, 0x00, 0x00, 0x00,   // checksum urgent Ptr     

84

                0x41, 0x42, 0x42, 0x44    // Data: "ABCD"

85

            };

86

            return buffer;

87

        }

88

89

90

        static void Main(string[] args)

91

        {       

92

            byte[] buffer = GetPseudoHeaderFrame();

93

            string hexCRC = InternetChecksum(buffer).ToString("X4");            

94

            Console.WriteLine(hexCRC);

95

        }

96

    }

97

}

Checksum: 28A6


Man beachte: Es handelt sich dabei um eine CRC16 (ersinnt in den 1970er 
Jahren).

Man stelle sich vor: Die Ethernet-Leitung ist defekt und 90% der Daten 
sind verfälscht....

In der Medizin-Technik verschickt man auf Anwendungsebene unter 
Umständen zu jedem Wichtigen Wert eine CRC32. Eine CRC32 Gesamtprüfsumme 
wird auf Anwendungsebene immer mitgeschickt. Also bin ich nicht der 
Einzige der sich lächerlich macht.

Doktoren, Physiker, Mathematiker machen das alles aus reinem 
Geltungsbedürfnis.

Men beachte es gibt 65535 = 2^16 Möglichkeiten einen Bytestream als 
Prüfsumme  darzustzustellen. Wie hoch ist die Wahrscheinlichkeit dass 
man bei Fehler die richtige Redundanz erwischt?

Jemand schrieb:
> Was hat TCP mit CRC zu tun? TCP nutzt kein CRC!

siehe:

https://de.wikipedia.org/wiki/Transmission_Control_Protocol#Aufbau_des_TCP-Headers

checksum



CRC32 wird nur auf Anwendungsebene verwendet.

Das Konzept vom TCP ist trotz Allem genial und ist allem Bekanntem 
überlegen. Die Leute hatten die Fähigkeit die Notwenigkeiten der Zukunft 
vorherzusagen.

Genial!

Andreas V. schrieb:
> Demnach gibt es 9 999 999 999 - 2^32 = 5 705 032 703 doppelte CRC's.

Das mit dem Doppelten ist so in der Form nahezu irrelevant.

Selbst wenn es zu jedem Wert eine Dublette geben würde wäre die 
Wahrscheinlichkeit das eine Fehler genau diese Dublette erzeugt immer 
noch sehr gering im Verhältnis zu den Fehlern die einen der anderen 
(2^32)-2 möglichen Werte erzeugt.
Ergibt also irgendwas um die die 2 zu 2^32 und nicht die Hälfte wie 
deine Werte dir versuchen zu suggerieren (die Leute die richtig Ahnung 
von Wahrscheinlichkeitstheorie und Stochastik haben können das 
wahrscheinlich genauer berechnen).

Also wenn du wirklich 5% nicht durch TCP/CRC erkannte Fehler hättest 
wäre der Anteil der erkannten Fehler (die im TCP in der Regel zu einer 
Retransmission führen) zum ein zigfaches höher. Deine Verbindung müsste 
eigentlich bis zum bersten voll sein alleine nur von den 
Retransmissionen.

Ein kurzer Blick mit z.B. Wireshark in die Datenpakete auf der 
Schnittstelle sollte sowas eigentlich recht schnell und zuverlässig 
aufdecken.

Andreas V. schrieb:
> In der Medizin-Technik verschickt man auf Anwendungsebene unter
> Umständen zu jedem Wichtigen Wert eine CRC32. Eine CRC32 Gesamtprüfsumme
> wird auf Anwendungsebene immer mitgeschickt. Also bin ich nicht der
> Einzige der sich lächerlich macht.
>
> Doktoren, Physiker, Mathematiker machen das alles aus reinem
> Geltungsbedürfnis.
>
> Men beachte es gibt 65535 = 2^16 Möglichkeiten einen Bytestream als
> Prüfsumme  darzustzustellen. Wie hoch ist die Wahrscheinlichkeit dass
> man bei Fehler die richtige Redundanz erwischt?

Die Wahrscheinlichkeit auf unerkannte Fehler ist zwar gering aber eben 
nicht null. Von daher ist es als Designpatern durchaus üblich das jede 
Schicht die auf die Unversehrtheit der übertragen Daten wert legt sich 
selbst darum kümmert und sich nicht alleine auf darunterliegende 
verlässt -frei nach "traue etwas nur wenn du es selbst geprüft hast".

Da braucht nur irgendeiner die Übertragung auf UDP umstellen und ein 
anderer am Hub die Karten zu tauschen um einen Fehler einzugrenzen. Wenn 
dann die Anwendung denkt alles was ankommt ist geprüft und überprüft 
selbst nichts mehr -> eine lustige fehlersucherei geht los...
Dazu muss man noch nichtmal im Medizinbereich unterwegs sein um so eine 
Annahme "die darunterliegende Schicht wird sich schon drum kümmern" 
zukünftig nicht mehr so leichtfertig zu machen.

Bei IP geht die Checksum nur über den Header! Alles andere ist nicht 
seine Aufgabe....


BTW: Ich habe eine interessante Diskussion dazu gefunden:

https://www.evanjones.ca/tcp-and-ethernet-checksums-fail.html

Das werde ich mir heute abend noch genauer anschauen.