Title of Invention

"METHOD AND ARRANGEMENT FOR FORMING AND CHECKING A CHECKSUM FOR DIGITAL DATA WHITCH ARE GROUPED INTO A NUMBER OF DATA SEGMENTS"

Abstract Method and arrangement for forming and checking a checksum for digital data which are grouped into a number of data segments Methods and arrangements for forming a checksum and for checking a checksum for digital data which are grouped into a number of data segments are specified. In the method, a checksum is formed for each data segment. The individual checksums are combined to form a first commutative checksum by using a commutative operation. To check the first commutative checksum, a checksum is again formed for each data segment and the checksum is again combined to form a second commutative checksum using a commutative operation. The first commutative checksum and the second commutative checksum are checked for a match.
Full Text -1A-
Description
Method and arrangement for forming and checking a checksum for digital data which are grouped into a number of data segments
In digital communications, i.e. during the exchange of digital data, it is frequently desirable to protect the transmission of the electronic data with respect to the most varied aspects.
A very significant aspect is the protection of the digital data to be transmitted against unauthorized modification, the so-called protection of the integrity of the data.
As a protection against unauthorized modification of digital data, the so-called cryptographic checksum, for example the digital signature, is known from [1]. The method described in [1] is based on forming a hashing value from the digital user data and the subsequent cryptographic processing of the hashing value by means of a cryptographic key. The result is a cryptographic checksum. To check the integrity, a corresponding cryptographic key is used for performing the inverse cryptographic operation on the checksum formed and the result is compared with the hashing value again calculated from the user data. The integrity of the user data is ensured when the hashing values are matched.
This previously customary procedure necessitates that the complete user data must be present on the receiver side in the identical order in which they were present when the hashing value was formed since otherwise the formation of the hashing value leads to an errored value. In digital communications, however, it is frequently customary to subdivide and to transmit the user data to be transmitted in relatively small data segments which are

also called data packets, due to protocol boundary conditions. The data segments are frequently not tied to a defined order or it is not possible to guarantee a defined sequential arrival of the data segments. In the method from [1] , it is therefore required for the complete user data to be reassembled again on the receiver side, that is to say after the transmission of the data segments, in the order in which they were originally sent. The data to be transmitted can only be verified in this order. However, this frequently means considerable additional expenditure for the flow control of the data segments inasmuch as this is possible at all within the framework of the protocol used.
From [2], commutative operations are known. In [2] , a general definition for commutative operations is also specified. Illustratively, a commutative operation can be understood to be an operation in which the order of individual operations is unimportant and each order of individual operation always leads to the same total operation. A commutative operation can be, for example, an EXOR operation, an additive operation or also a multiplicative operation.
From [3] , a method and a device for generating check code segments for the occurrence of source data and for determining errors in the source data are known.
The invention is thus based on the object of specifying methods and arrangements for forming and checking a first commutative checksum for digital data which are grouped into a number of data segments, in which a flow control for the individual data segments is no longer required.
The object is achieved by the method according to Claim 1, by the method according to Claim 2, by the method according to Claim 3, by the arrangement according to Claim 11, by the arrangement according to Claim 12 and by the arrangement according to Claim 13.

3
In the method according to Claim 1, a first segment checksum is formed for each data segment for digital data which are grouped into a number of data segments. The first segment checksums formed are combined by a commutative operation to form a first commutative checksum.
In the method according to Claim 2, a predetermined first commutative checksum, which is allocated to digital data which are grouped into a number of data segments, is checked. This is done by a second segment checksum being formed for each data segment and a second commutative checksum being formed by a commutative operation on the second segment checksum. The second commutative checksum and the first commutative checksum are checked for a match.
In the method according to Claim 3 for forming and checking a first commutative checksum for digital data which is grouped into data segments, a first segment checksum is formed for each data segment and the first data checksums are combined by a commutative operation to form a first commutative checksum. For each data segment of the digital data to which the first commutative checksum is allocated, second segment checksums are formed and a second commutative checksum is formed by commutative operation on the second segment checksums. The second commutative checksum and the first commutative checksum are checked for a match.
The arrangement according to Claim 11 exhibits an arithmetic and logic unit which is arranged in such a manner that a segment checksum is formed for each data segment and that the first commutative checksum is formed by a commutative operation on the segment checksums.
The arrangement according to Claim 12 exhibits an arithmetic and logic unit which is arranged in such a manner that a second segment checksum is formed for each data segment, a second commutative checksum is formed by a commutative operation on the second segment checksums, and the second commutative checksum (KP2) is

checked for a match with the first commutative checksum (KP1).
The arrangement according to Claim 13 exhibits an arithmetic and logic unit which is arranged in such a manner that the following method steps are performed:
a) a segment checksum is formed for each data segment,
b) the first commutative checksum is formed by a
commutative operation on the segment checksums,
c) a second segment checksum is formed for each data
segment of the digital data to which the fxrst
commutative checksum is allocated,
d) a second commutative checksum is formed by a
commutative operation on the second segment checksums,
and
e) the second commutative checksum is checked for a
match with the first commutative checksum.
A considerable advantage of the methods and of the arrangements can be seen in the fact that, by using a commutative operation for individual checksums of the data segments, a flow control for the order of the individual data segments is no longer required.
Furthermore, it is no longer required to reassemble the complete user data in the original order in which the first commutative checksums were formed. The order of the individual data segments is no longer of significance in the formation of the commutative checksum.
If the digital data are transmitted between two arrangements, a further advantage of the methods can be seen in the fact that the checking of the integrity can already be begun before all data segments have been received since it is no longer required to maintain the original order in forming the first checksum. This leads to a timesaving in the checking of the integrity of the data.
Illustratively, the invention can be seen in the fact that a checksum is formed in the case of a number of data segments which, together, form the data to be protected, and the individual checksums of the

data segments are commutatively combined with one another.
Advantageous further developments of the invention are obtained from the dependent claims.
It is advantageous to protect the first commutative checksum cryptographically by using at least one cryptographic operation.
The result of this further development is that the cryptographic security of the data is considerably increased. A cryptographic operation in this sense is, for example, the encrypting of the first commutative checksum with a symmetric or also with an assymetric encryption method which forms a cryptographic checksum. On the receiver side, the inverse cryptographic method to the cryptographic method is performed in order to ensure cryptographic security.
To form a checksum within the context of the document, various possibilities are known:
- a checksum can be formed by forming hashing values
for the individual data segments;
- the checksums can also be formed by so-called cyclic
codes (Cyclic Redundancy Check, CRC);
- a cryptographic one-way function can also be used for
forming the checksums for the data segments.
The methods can be advantageously used in various application scenarios.
The methods can be used both in the transmission of digital data for protection against manipulation of the data, and in the archiving of digital data in a computer in which the first commutative checksum is formed and stored together with the data to be archived. The first commutative checksum can be checked when the digital data are loaded from the archive memory in order to detect any manipulation of the archived data.
The method can be advantageously used for protecting digital data, the data segments of which are not tied to an order. Examples of such data segments are packet-oriented communication protocols, for

6
example network management protocols such as the Simple Network Management protocol {SNMP) or the Common Management Information protocol (CMIP).
In the text which follows, an illustrative embodiment of the invention will be explained in greater detail with reference to a Figure. Even if the illustrative embodiment is explained with reference to the Simple Network Management Protocol (SNMP) in the text which follows, this does not represent any restriction on the applicability of the method. The method can be used whenever it is of importance to ensure integrity protection for digital data which are grouped into a number of data segments.
The Figure shows two arrangements, data segments being transmitted from the first arrangement to the second arrangement.
In the Figure, a first computer arrangement Al, in which data segments (Di, i = 1 .. n) are stored, is shown symbolically. The data segments Di together form the digital data which are also designated as user data, for which xt is of importance to ensure their integrity.
Both the first computer arrangement Al and a second computer arrangement A2 described in the text which follows in each case contain an arithmetic and logic unit R which is arranged in such a manner that the method steps described in the text which follows are performed.
In the first arrangement Al, the data segments Di are arranged at positions Pi within the total data stream. For each data segment Di, a first segment checksum PSi is formed by using a checksum function PSF. The individual first segment checksums PSi are combined to form a first commutative checksum KPl by a commutative operation as defined and described in [2] . The commutative operation on the individual checksums PSi is shown symbolically by an EXOR symbol in the Figure.

7
The first commutative checksum KP1 is subjected to a cryptographic method, a symmetric or asymmetric method, by using a first cryptographic key S (step 101) . The result of the cryptographic operation is a cryptographic checksum KP.
Both the data segments Di and the cryptographic checksum KP are transmitted by a transmission medium, preferably a line or also a logical connection which is symbolically shown by a communication link UM in the Figure, to a second arrangement A2 where they are received.
The crossing arrows of the data segments Di in the Figure indicate that, due to the transmission of the data segments Di, these are received in positions Pj (j = a . . z) which are displaced compared with the order in the first arrangement Al.
Thus, a data segment D2 at the first position P1 is received as data segment Da in the second arrangement A2. Data segment D1 is received as data segment Dc in the second arrangement. Data segment Dn is received as received data segment Db at the second position P2 in the second arrangement A2.
In accordance with the method used, either the first cryptographic key S is used for performing the inverse cryptographic operation on the cryptographic checksum KP if a symmetric encryption method is used, or a second cryptographic key S' is used if an asymmetric cryptographic method is used.
The result of the inverse cryptographic operation (step 102) is again the first commutative checksum KP1 with correct encryption and decryption.
This checksum is stored in the second arrangement A2. For the comparison of the data segments Dj, which are now received in permutated order compared with the original order during the formation of the first commutative checksum KP1, second segment checksums Psj are formed for the received data segments Dj, again using the same checksum methods PSF.

8
The resultant second checksums PSj are again commutatively combined with one another to form a second commutative checksum KP2.
In a further step 103, a check is made whether the first commutative checksum KP1 matches the second commutative checksum KP2.
If this is so, the integrity of the data segments Di, and thus the integrity of all the digital data, is ensured {step 104) if the cryptographic methods used or, respectively, the methods used for forming checksums ensure the corresponding cryptographic security.
If the first cryptographic checksum KPl does not match the second cryptographic checksum KP2, the integrity of the data segments Di would be violated and a manipulation of the data is found and preferably reported to a user of the system.
The protocol data units (PDU) in SNMP are structured in such a manner that the user information (so-called variable bindings) can contain a list of objects (object indicators, OID/value pairs). The order of the objects within a PDU is not specified so that it is possible for a permutation of the objects to occur during the transmission of the PDUs between the first arrangement Al and the second arrangement A2. The invention now makes it possible to form a single cryptographic checksum over all objects of an SNMP PDU without having to take into consideration the order of the objects or of the PDUs.
In the text which follows, alternatives to the illustrative embodiment described above will be explained.
The method for forming the checksum PSF can be, for example, a method for forming hashing values. However, methods for forming cyclic codes (Cyclic Redundancy Check, CRC) using feedback-type shift registers can also be used. In addition, cryptographic one-way functions can be used for forming the checksums PSi and, respectively, Psj.

Furthermore, the commutative operation can have the additional property of associativity.
Both the method for forming the checksum and the method for checking a checksum can be performed independently of one another. However, the method for forming the checksum and the method for checking the checksum can also be performed jointly.
Furthermore, it is provided not to transmit digital data but to archive the digital data, that is to say to store them in the first arrangement Al, together with the first commutative checksum KP1. When the archived data are reused, that is to say when the data segments Di are loaded from the memory of the first arrangement Al, the method for checking the first commutative checksum KP1 as described above will then be performed. The first arrangement Al and the second arrangement A2 can thus be identical.
Illustratively, the invention can be seen in that in the case of a number of data segments which, together, represent the data to be protected, a checksum is formed for each data segment and the individual checksums of the data segments are commutatively combined with one another. This makes it possible to form and to check a checksum without having to take into consideration the order of the data segments.
In this document, the following publications have been quoted: [1] W. Stallings, Sicherheit in Netzwerk und Internet
(Security in Network and Internet), Prentice Hall,
ISBN 3-930436-29-9, pp. 203-223, 1995 [2] K.-H. Kiyek and F. Schwarz, Mathmatik fur
Informatiker (Mathematics for Computer
Scientists), Teubner Verlag, ISBN 3-519-03277-X,
pp. 11-13, 1989 [3] DE-A 2 048 365

10
WE CLAIM:
1. Method for forming a cryptographic commutative checksum (KP) for digital data which are grouped into a number of data segments (Di, i = l..n), by a computer,
a) in which a segment checksum (PSi) is formed for each data segment
(Di),
b).in which a first commutative checksum (KP1) is formed by a commutative operation (©) on the segment checksums (PSi) and
c) in which the first commutative checksum (KP1) is cryptographically protected using at least one cryptographic operation, with the cryptographic commutative checksum (KP) being formed,
2. Method for checking a predetermined cryptographic commutative checksum (KP) which is allocated to digital data which are grouped into a number of data segments, by a computer,
a) in which the cryptographic commutative checksum (KP) is subjected to
an inverse cryptographic operation in order to form a first commutative
checksum (KP1),
b) in which a second segment checksum (PSj) is formed for each data
segment (Dj,j = a ..z),
c) in which a second commutative checksum (KP2) is formed by a
commutative operation () on the second segment checksums (PSj),
and
d) in which the second commutative checksum (KP2) is checked for a
match with the first commutative checksum (KP1).
3. Method according to claim 1 and claim 2 for forming and checking a cryptographic commutative checksum (KP) for digital data which are grouped into a number of data segments (Di, i = 1 ..n), by a computer,
a) in which a segment checksum (PSi) is formed for each data segment (Di),
b) in which a first commutative checksum (KP1) is formed by a commutative
operation () on the segment checksums (PSI),

11
c) in which the first commutative checksum (KP1) is cryptographicaliy
protected using, at least one cryptographic operation, with the
cryptographic commutative checksum (KP) being formed.
d) in which the cryptographic commutative checksum (KP) is subjected to an
inverse cryptographic operation in order to form a first reconstructed
commutative checksum (KP1),
e) in which a second segment checksum (PSj) is formed for each data
segment (Dj, j = a .. z) of the digital data to which the first commutative
checksum (KP1) is allocated,
f) in which a second commutative checksum (KP2) is formed by a
commutative operation () on the second segment checksums (PSj), and
g) in which the second commutative checksum (KP2) is checked for a match
with the first reconstructed commutative checksum (KP1).
4. Method according to one of claims 1 to 3, in which the segment checksums
(PSi, PSj) are formed in accordance with at least one of the following types:
- forming a hashing value,
- forming CRC codes,
- using at least one cryptographic one-way function.

5. Method according to one of claims 1 to 4, in which the cryptographic
operation is a symmetric cryptographic method.
6. Method according to claims 1 to 4, in which he cryptographic operation rs an
asymmetric cryptographic method.
7. Method according to one of claims 1 to 6, in which the commutative operation
() exhibits the property of associavity.

12
8. Method according to one of claims I to 7, in which digital data are protected,
the data segments (Di) of which are not tied to an order.
9. Method according to-one of claims 1 to 7, in which digital data are protected
which are processed in accordance with a network management protocol.
10. Arrangement for forming a cryptographic commutative checksum (KP) for
digital data which are grouped into a number of data segments (Di, i = 1.. n), by
means of an arithmetic and logic unit which is arranged in such a manner that

a) a segment checksum (PSi) is formed for each data segment (Di),
b) a first commutative checksum (KP1) is formed by a commutative
operation () on the segment checksum (PSi). and
c) the first commutative checksum (KP1) is cryptographically protected by
using at least one cryptographic operation,
with the cryptographic commutative checksum (KP) being formed.
11. Arrangement for checking a predetermined cryptographic commutative checksum (KP) which is allocated to digital data which are grouped into a number of data segments, by means of an arithmetic and logic unit which is arranged in such a manner that
a) the cryptographic commutative checksum (KP) is subjected to an inverse cryptographic operation in order to form a first commutative checksum
(KP1),

13
b) a second segment checksum (PSj) is formed for each data segment (Dj, j
= a .. z),
c) a second commutative checksum (KP2) formed by a commutative
operation () on the second segment checksum (PSj), and
d) the second commutative checksum (KP2) is checked for a match with the
first commutative checksum (KP1).
12.Arrangement according to claim 10 and claim 11 for forming and checking a cryptographic commutative checksum (KP) for digital data which is grouped into a number of data segments (Di, i = 1 .. n), by means of at least one arithmetic and logic unit which is arranged in such a manner that
a) a segment checksum (PSj) is formed for each data segment (Di),
b) a first commutative checksum (KP1) is formed by a commutative
operation () on the segment checksums (PSi),
c) the first commutative checksum (KP1) is cryptographicaIly protected
using at least one cryptographic operation, with the cryptographic
commutative checksum (KP) being formed,
d) the cryptographic commutative checksum (KP) is subjected to an inverse
cryptographic operation in order to form a first reconstructed
commutative checksum (KP1),
e) a second segment checksum (PSj) is formed for each data segment (Dj, j
= a .. z) of the digital data to which the first commutative checksum
(KP1) is allocated,
f) a second commutative checksum (KP2) is farmed by a commutative
operation () on the second segment checksums (PSj), and
g) the second commutative checksum (KP2) is checked for a match with the
first reconstructed commutative checksum (KP1).

14
13. Arrangement according to one of claims 10 to 12, in which the arithmetic and logic unit is arranged in such a manner that the segment checksums (PSi,PSj) are formed in accordance with at least one of the following types :
- forming a hashing value,
- forming CRC codes,
- using at least one cryptographic one-way function.
14. Arrangement according to one of claims 10 to 13, in which the arithmetic and
logic unit is arranged in such a manner that the cryptographic operation is a
symmetric cryptographic method.
15. Arrangement according to one of claims 10 to 13, in which the arithmetic and
logic unit is arranged in such a manner that the cryptographic operation is an
asymmetric cryptographic method.
16. Arrangement according to one of claims 10 to 15, in which the arithmetic and
logic unit is arranged in such a manner that the commutative operation ()
exhibits the property of associativity.
17. Arrangement according to one of claims 10 to 16, in which the arithmetic and
logic unit is set up in such a manner that the digital data are protected, the
data segments (Di) of which are not tied to an order.

15
18.Arrangement according to one of claims 10 to 16, in which the arithmetic and logic unit is arranged in such a manner that the digital data are protected which are processed in accordance with a network management protocol.
Method and arrangement for forming and checking a checksum for digital data which are grouped into a number of data segments
Methods and arrangements for forming a checksum and for checking a checksum for digital data which are grouped into a number of data segments are specified. In the method, a checksum is formed for each data segment. The individual checksums are combined to form a first commutative checksum by using a commutative operation. To check the first commutative checksum, a checksum is again formed for each data segment and the checksum is again combined to form a second commutative checksum using a commutative operation. The first commutative checksum and the second commutative checksum are checked for a match.

Documents:

00391-cal-1998 abstract.pdf

00391-cal-1998 claims.pdf

00391-cal-1998 correspondence.pdf

00391-cal-1998 description (complete).pdf

00391-cal-1998 drawings.pdf

00391-cal-1998 form-1.pdf

00391-cal-1998 form-2.pdf

00391-cal-1998 form-3.pdf

00391-cal-1998 form-5.pdf

00391-cal-1998 g.p.a.pdf

00391-cal-1998 letters patent.pdf

00391-cal-1998 priority document others.pdf

00391-cal-1998 priority document.pdf


Patent Number 202635
Indian Patent Application Number 391/CAL/1998
PG Journal Number 09/2007
Publication Date 02-Mar-2007
Grant Date 02-Mar-2007
Date of Filing 10-Mar-1998
Name of Patentee SIEMENS AKTIENGESELLSCHAFT
Applicant Address Wittelsbacherplatz 2, 80333 Munchen,
Inventors:
# Inventor's Name Inventor's Address
1 KIAUS LUKAS Niemoellerallee 6, 81793 Muenchen,
2 MARTINA HANCK AM Grenzweg 2, 85635 Hoehenkirchen,
3 GERHARD HOFMANN Gozbertstr. 8/11, 81547 Muenchen,
PCT International Classification Number H 04L 9/32
PCT International Application Number N/A
PCT International Filing date
PCT Conventions:
# PCT Application Number Date of Convention Priority Country
1 19715486.7 1997-04-14 Germany