+

WO1994021066A1 - Procede et appareil pour generer un code d'authentification d'un message numerique - Google Patents

Procede et appareil pour generer un code d'authentification d'un message numerique Download PDF

Info

Publication number
WO1994021066A1
WO1994021066A1 PCT/AU1994/000101 AU9400101W WO9421066A1 WO 1994021066 A1 WO1994021066 A1 WO 1994021066A1 AU 9400101 W AU9400101 W AU 9400101W WO 9421066 A1 WO9421066 A1 WO 9421066A1
Authority
WO
WIPO (PCT)
Prior art keywords
message
cipher
sequence
generating
authentication code
Prior art date
Application number
PCT/AU1994/000101
Other languages
English (en)
Inventor
Richard Taylor
Original Assignee
Telstra Corporation Limited
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Telstra Corporation Limited filed Critical Telstra Corporation Limited
Priority to AU62556/94A priority Critical patent/AU683646B2/en
Publication of WO1994021066A1 publication Critical patent/WO1994021066A1/fr

Links

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/06—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols the encryption apparatus using shift registers or memories for block-wise or stream coding, e.g. DES systems or RC4; Hash functions; Pseudorandom sequence generators
    • H04L9/065—Encryption by serially and continuously modifying data stream elements, e.g. stream cipher systems, RC4, SEAL or A5/3
    • H04L9/0656—Pseudorandom key sequence combined element-for-element with data sequence, e.g. one-time-pad [OTP] or Vernam's cipher
    • H04L9/0662—Pseudorandom key sequence combined element-for-element with data sequence, e.g. one-time-pad [OTP] or Vernam's cipher with particular pseudorandom sequence generator
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/06—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols the encryption apparatus using shift registers or memories for block-wise or stream coding, e.g. DES systems or RC4; Hash functions; Pseudorandom sequence generators
    • H04L9/0643—Hash functions, e.g. MD5, SHA, HMAC or f9 MAC

Definitions

  • This invention relates to a method and apparatus for generating a digital message authentication code.
  • B-ISDN broadband integrated systems digital networks
  • digital messages are often encrypted or enciphered such that a person intercepting the transmitted message is unable to ascertain its meaning. Therefore, at the sending site on the network a plain text message is, under control of an enciphering key, transformed into cipher text which is preferably unintelligible to anyone not having the secret deciphering key.
  • the cipher text is, under control of the secret deciphering key, retransformed into the original plain text message.
  • Stream ciphers act by dividing the plain text into characters, each of which is enciphered utilising a time varying function whose time dependency is governed by the internal state of the stream cipher.
  • the time varying function is produced by a cipher stream generator, which generates a digital cipher stream in accordance with key data which is kept secret.
  • the cipher stream generator is constructed such that the cipher stream produced is a pseudo random bit stream which is cyclic, but has a period which is much greater than the length of key data provided.
  • the device changes state according to a rule, such that two occurrences of the same character in the plain text message will usually not result in the same cipher text character.
  • the security or strength of a stream cipher depends on the "randomness" of the generated cipher stream. Assuming an interceptor has knowledge of the plain text message, full access to the running cipher stream may also be deduced. For the system to be secure, the cipher stream must be unpredictable: regardless of the number of cipher stream digits observed, the subsequent cipher stream digits must not be more easily predictable than by just randomly guessing them. An enciphering system such as this ensures that an unauthorised person is unable to determine the meaning of an intercepted message, but does not address the issue of interference with the message despite its meaning being unknown. For example, a portion of a transmitted message may be intercepted altered or replaced with another message portion even if the interceptor is unable to ascertain the deciphered meaning of the original, altered or replaced message portion.
  • a message authentication code (mac), or integrity check value (icv) determined from the content of the plain text message may be transmitted with the cipher text to enable the receiver to determine whether the received deciphered plain text corresponds with the plain text originally transmitted, i.e. whether the cipher text has been altered during transmission.
  • the message deciphering and authentication process involves the receiver having access to a cipher stream corresponding to the cipher stream with which the message was enciphered.
  • the receiver can decipher it and generate a mac from the deciphered plain text message.
  • a comparison of the received mac and the mac generated by the receiver can then be used as an indication of whether the transmitted mac or message has been altered in transit, since the mac generated by the receiver should be the same as the mac generated at the transmitter.
  • a cryptanalyst it may be possible for a cryptanalyst to alter both the cipher text message and the enciphered mac in such a way that the change is not apparent to the receiver, even though the cryptanalyst is unable to determine the meaning of the cipher text which has been altered.
  • a paper entitled “A Fast Cryptographic Checksum Algorithm Based on Stream Ciphers” (X. Lai, R. Reuppel, J. Woollven; AUSCRYPT “92 Abstracts; pp 8-7 to 8-11) describes a cryptographic checksum algorithm for producing a message authentication code with a stream cipher system.
  • the checksum algorithm presented involves demultiplexing the message stream into two subsequences according to the binary state of the cipher stream. The two subsequences are input to respective accumulating feedback shift registers, the outputs of which serve as a pair of message authentication codes.
  • a method for generating a message authentication code for a digital message in a telecommunications or computer system comprising:
  • the message comprises a sequence of message units which are multiplied by respective powers of said first cipher string in generating the message authentication code.
  • the message comprises a sequence of message blocks each comprising a said sequence of message units, each sequence of message units being multiplied by respective different said first cipher strings and summed with said second cipher string to form the message authentication code.
  • a method for generating a message authentication code in a telecommunications or computer system for a digital message which comprises a sequence of message blocks each comprising a sequence of message units, including the steps of:
  • the message units are multiplied by respective powers of a said cipher string sequence value.
  • the present invention further provides a method for encoding a digital message comprising generating a sequence of cipher strings, generating a message authentication code according to a method described above, enciphering the message by combining at least one said cipher string therewith, the at least one cipher string being distinct from the cipher strings utilised for generating the message authentication code, and appending the message authentication code to the enciphered message.
  • the invention also provides apparatus for generating a message authentication code for a digital message composed of a sequence of message blocks, comprising: a stream cipher for generating a sequence of pseudo-random cipher strings; and computation means for generating a non-linear function value for each message block by combining each message block with at least one said cipher string by way of modular arithmetic to a prime modulus, and generating a message authentication code by summing the non-linear function values together with at least one further said cipher string.
  • Figure 1 is a flow chart of a preferred algorithm for generating a message authentication code
  • Figure 2 is a block diagram of a system for encoding digital messages for transmission by way of a telecommumcations path.
  • An effective cipher stream generator utilises secret key data to produce an output consisting of a pseudo random bit stream Z.
  • the cipher stream Z is typically used to encrypt a stream of message data by logically combining the cipher stream and the message stream. Since the cipher stream is continuously changing, a particular bit sequence repeated in the message stream will be encrypted differently each time, depending on the state of the cipher stream. It is therefore advantageous to exploit the time dependence randomness of the cipher stream not only for encryption of the message, but also to ensure that the integrity of the message is not compromised.
  • message authenticity and message integrity are used interchangeably to refer to the condition of a digital message reaching its destination unaltered or, if altered, the alteration being detectable at the destination.
  • message authentication code (mac) and integrity check value (icv) are used interchangeably throughout the specification to denote a numerical value generated from the numerical value of a message which may be utilised to determine whether the message itself has been altered before reaching its destination.
  • t[u] to represent the unique positive integer satisfying: t[u] ⁇ t(mod u) and 0 ⁇ t[u] ⁇ (u-1)
  • the output of the cipher stream may be used to provide message integrity by the construction of an integrity check value (icv) that is generated from the message and appended thereto.
  • a non-linear combination of the message and the stream cipher output is utilised to prevent an attacker from modifying the message and determining the necessary modification to generate a valid icv.
  • Prime power modular arithmetic is also used in generating the icv, which ensures that the values of the icv are uniformly distributed and minimal in number for a given message value.
  • the preferred implementation of the integrity check value generation involves generating a single icv for a message which consists of a sequence of message blocks each comprising a sequence of message integer units.
  • M s m bs , m bs+1 ,..., m bs+1 , for some t ⁇ b-1
  • the icv is calculated as: icv(M, b, p, z i , z i+1 ,..., z i+s+1 )
  • the following example illustrates the procedure for generation of an icv for transmission with a message, such as over a telecommumcations network.
  • the cipher is used to generate 7 outputs z 56 , z 57 , z 58 ,..., z 62 , and the integrity check value is calculated according to (1) and (2).
  • the transmitted message is then m 0 , m 1 ,..., m 108 icv.
  • the strength of the message integrity or authentication checking system is preferably of the same order as the strength of the accompanying encryption system. In other words, the probability that an attacker is able to alter a message undetected should be comparable to the probability of the attacker successfully deciphering the message.
  • Corollary 1 is an immediate consequence of this theorem.
  • Corollary 1 Let M and M' be any two unequal message strings, and y any fixed integer. Let the function icv() be defined as in (1) and (2). Then if z i , z i+1 , z i+2 ,..., z i+s are independent and uniformly distributed random variables in the range 0 to 2 w -l,
  • Corollary 2 indicates the strength of the integrity mechanism in terms of the likelihood of replacing, in transit, a message and the corresponding icv with a legitimate, but different, message-icv pair.
  • Corollary 2 Let M and M' be any two unequal message strings, and y, g any fixed integers. Let the function icv() be defined as in (1) and (2). Then if z i , z i+1 , z i+2 ,..., z i+s , Z i+s+1 are independent and uniformly distributed random variables in the range 0 to 2 w -1,
  • the stream cipher produces output that are independent and uniformly distributed random variables in the range 0 to 2 w -1. It follows from Corollary 2 that if any message and its integrity check value were to be altered in transit (the message being altered in at least one bit position), the new message and integrity check value would register as valid by the receiver with probability at most b/2 w . Thus we refer to log 2 (2 w /b) as the effective icv size. As an example, with a word size w of 32 bits and a block size b of 20 the resulting effective icv size is approximately 28. Note that the effective icv size indicates the strength of the integrity method used with an idealised stream cipher (with outputs that are uniformly distributed independent random variables).
  • the stream cipher key size must be at least as large as the effective icv size. In this case if there is some way of altering or substituting message-icv pairs that goes undetected with a probability of more than b/2 w then this implies some corresponding level of predicability in the stream cipher output.
  • Figure 1 illustrates a flow chart of the preferred method of generating an integrity check value (icv) or message authentication code (mac).
  • the flow chart 2 is structured into a dual loop iterative process, wherein steps 6, 8, 12 and 18 are used for the calculation of non linear function y (equation (2)) whilst steps 16, 20 and 22 perform the steps necessary for the calculation of the icv according to equation (1).
  • Step 6 acts as an initialisation step for the non linear function value y, such that the first iteration of steps 8 and 12 are effective to calculate the first term of equation (2) (ie: n 0 x).
  • steps 8 and 12 successive integer values of the message are input from the message stream 10 and values of the stream cipher are input from cipher stream 14 according to the message block counter index k.
  • the index j is incremented by one, and a test of the value of index j is applied at step 16 to determine whether or not the last unit of the message has been processed. Where there remains message units left to process, the procedure continues to step 18 where a test is applied to index j to determine whether or not the end of a message block has been reached.
  • step 18 If j+1 is an integer divisor of block size b at step 18, this indicates that the beginning of a new message block has been reached, and the procedure continues to step 20 where the icv is incremented by the value of the non linear function y.
  • the block counter index k is incremented following step 20, and the procedure passes to step 6 where the non linear function y is reset. Where the beginning of a message block has not been reached at step 18 the procedure returns to step 8, so as to perform a further iteration of steps 8, 12 and 16.
  • the block counter index k is again incremented and the icv is totalled together with the final stream cipher value z k (step 22).
  • this method allows the icv to be calculated in a serial manner, which is consistent with the continuous output form of the message stream and cipher stream.
  • a message string M (m 0 , m 1 ,...) is divided into blocks M 0 , M 1 ,..., M s each contaimng at most b integers.
  • the stream cipher is used to generate h(s+2) outputs z i , z i+1 , z i+2 ,..., z i+h(s+2)-1 .
  • the integrity check value icv h is defined as a sequence of h integers between 0 and p calculated according to: icv h (M, b, p, z i , Z i+1 ,..., z i+h(s+2)-1 )
  • the cipher stream can be used to provide input to the integrity calculation as well as output to be used for message encryption.
  • cipher stream output that is used in icv calculations by the receiver never be used for message encryption by the sender. Otherwise a known plaintext attack combined with altering the synchronisation of the cipher stream may succeed in making the receiver use cipher data in icv calculations which is known to an attacker.
  • an integer d ( ⁇ b) is chosen such that only those z i for which i is a multiple of d are used in the icv calculation, the remaining z i being used for encryption. This technique is illustrated in the example below.
  • the transmitted message is
  • FIG. 2 illustrates a simple block diagram of an encryption and integrity system which may be utilised to implement the above described.
  • Message data m j is output from a message source 26, which message data is passed to both an encryption processor 30 and a message authentication code generator 32.
  • a cipher stream generator 28 outputs stream cipher data z i , which also passes to both the encryption processor 30 and mac generator 32.
  • the encryption processor 30 acts to combine the message and cipher stream data so as to encrypt the message for transmission thereof.
  • the mac generator 32 produces an integrity check value, as described above, utilising the same message data but only one of out every d cipher stream outputs, the other d-1 cipher stream outputs being utilised for encryption by the encryption processor 30.
  • M j m bj , m bj+1 , ...., m b(j+1)-1
  • N n 0 , n 1 , n 2 , .... n r

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Security & Cryptography (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Power Engineering (AREA)
  • Storage Device Security (AREA)

Abstract

L'invention concerne un procédé et un appareil pour générer un code d'identification de message (mac) ou une valeur de vérification d'intégrité (icv) pour un message numérique destiné à être transmis par un moyen de télécommunication. On applique une arithmétique modulaire à un premier module pour combiner les données du message et les données du code pseudo-aléatoire de manière à produire un code mac ou une valeur icv ayant une force de codage comparable à celle de la source des données codées. Le procédé pour générer le code mac peut être mis en ÷uvre d'une manière itérative, ce qui convient bien à une utilisation avec les procédés de codage en train.
PCT/AU1994/000101 1993-03-05 1994-03-04 Procede et appareil pour generer un code d'authentification d'un message numerique WO1994021066A1 (fr)

Priority Applications (1)

Application Number Priority Date Filing Date Title
AU62556/94A AU683646B2 (en) 1993-03-05 1994-03-04 A method and apparatus for generating a digital message authentication code

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
AUPL771493 1993-03-05
AUPL7714 1993-03-05

Publications (1)

Publication Number Publication Date
WO1994021066A1 true WO1994021066A1 (fr) 1994-09-15

Family

ID=3776758

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/AU1994/000101 WO1994021066A1 (fr) 1993-03-05 1994-03-04 Procede et appareil pour generer un code d'authentification d'un message numerique

Country Status (1)

Country Link
WO (1) WO1994021066A1 (fr)

Cited By (11)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO1998015085A1 (fr) * 1996-10-01 1998-04-09 Deutsche Telecom Ag Procede de transmission de signaux
WO2000069206A1 (fr) * 1999-05-11 2000-11-16 Nokia Corporation Procede de protection de l'integrite d'une emission de signaux dans un reseau radio
US6941461B2 (en) * 2000-05-12 2005-09-06 International Business Machines Corporation System and method of uniquely authenticating each replication of a group of soft-copy documents
US7072868B2 (en) * 2003-02-20 2006-07-04 First Data Corporation Methods and systems for negotiable-instrument fraud prevention
US7571320B2 (en) * 1999-11-22 2009-08-04 Intel Corporation Circuit and method for providing secure communications between devices
US7933835B2 (en) 2007-01-17 2011-04-26 The Western Union Company Secure money transfer systems and methods using biometric keys associated therewith
US8504473B2 (en) 2007-03-28 2013-08-06 The Western Union Company Money transfer system and messaging system
US8818904B2 (en) 2007-01-17 2014-08-26 The Western Union Company Generation systems and methods for transaction identifiers having biometric keys associated therewith
DE102016219926A1 (de) * 2016-10-13 2018-04-19 Siemens Aktiengesellschaft Verfahren, Sender und Empfänger zum Authentisieren und zum Integritätsschutz von Nachrichteninhalten
JP2019016987A (ja) * 2017-07-10 2019-01-31 Ｎｅｃソリューションイノベータ株式会社 通信システム、管理装置、端末装置、通信方法、及びプログラム
CN112887079A (zh) * 2021-03-11 2021-06-01 中国石油大学(华东) 基于一段随机比特序列生成的变换加密算法

Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US3657476A (en) * 1970-01-23 1972-04-18 Howard H Aiken Cryptography
US4972474A (en) * 1989-05-01 1990-11-20 Cylink Corporation Integer encryptor
US5146500A (en) * 1991-03-14 1992-09-08 Omnisec A.G. Public key cryptographic system using elliptic curves over rings

Patent Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US3657476A (en) * 1970-01-23 1972-04-18 Howard H Aiken Cryptography
US4972474A (en) * 1989-05-01 1990-11-20 Cylink Corporation Integer encryptor
US5146500A (en) * 1991-03-14 1992-09-08 Omnisec A.G. Public key cryptographic system using elliptic curves over rings

Cited By (19)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7188361B1 (en) 1996-10-01 2007-03-06 Deutsche Telekom Ag Method of transmitting signals
WO1998015085A1 (fr) * 1996-10-01 1998-04-09 Deutsche Telecom Ag Procede de transmission de signaux
WO2000069206A1 (fr) * 1999-05-11 2000-11-16 Nokia Corporation Procede de protection de l'integrite d'une emission de signaux dans un reseau radio
US7246242B1 (en) 1999-05-11 2007-07-17 Nokia Corporation Integrity protection method for radio network signaling
US7571320B2 (en) * 1999-11-22 2009-08-04 Intel Corporation Circuit and method for providing secure communications between devices
US6941461B2 (en) * 2000-05-12 2005-09-06 International Business Machines Corporation System and method of uniquely authenticating each replication of a group of soft-copy documents
US7072868B2 (en) * 2003-02-20 2006-07-04 First Data Corporation Methods and systems for negotiable-instrument fraud prevention
US9123044B2 (en) 2007-01-17 2015-09-01 The Western Union Company Generation systems and methods for transaction identifiers having biometric keys associated therewith
US7933835B2 (en) 2007-01-17 2011-04-26 The Western Union Company Secure money transfer systems and methods using biometric keys associated therewith
US8818904B2 (en) 2007-01-17 2014-08-26 The Western Union Company Generation systems and methods for transaction identifiers having biometric keys associated therewith
US8504473B2 (en) 2007-03-28 2013-08-06 The Western Union Company Money transfer system and messaging system
US10311410B2 (en) 2007-03-28 2019-06-04 The Western Union Company Money transfer system and messaging system
DE102016219926A1 (de) * 2016-10-13 2018-04-19 Siemens Aktiengesellschaft Verfahren, Sender und Empfänger zum Authentisieren und zum Integritätsschutz von Nachrichteninhalten
CN110089068A (zh) * 2016-10-13 2019-08-02 西门子股份公司 用于认证和完整性保护消息内容的方法、发送器和接收器
CN110089068B (zh) * 2016-10-13 2020-10-30 西门子股份公司 用于认证和完整性保护消息内容的方法、发送器和接收器
EP3501136B1 (fr) * 2016-10-13 2021-06-23 Siemens Aktiengesellschaft Procédé, émetteur et récepteur permettant l'authentification et la protection d'intégrité de contenus de messages
US11288400B2 (en) 2016-10-13 2022-03-29 Siemens Aktiengesellschaft Method, transmitter, and receiver for authenticating and protecting the integrity of message contents
JP2019016987A (ja) * 2017-07-10 2019-01-31 Ｎｅｃソリューションイノベータ株式会社 通信システム、管理装置、端末装置、通信方法、及びプログラム
CN112887079A (zh) * 2021-03-11 2021-06-01 中国石油大学(华东) 基于一段随机比特序列生成的变换加密算法

Similar Documents

Publication Publication Date Title
US5703952A (en) Method and apparatus for generating a cipher stream
Rueppel Stream ciphers
US5799088A (en) Non-deterministic public key encrypton system
US7054445B2 (en) Authentication method and schemes for data integrity protection
EP0635956B1 (fr) Procédé et système de communication utilisant un dispositif cryptographique
US20020048364A1 (en) Parallel block encryption method and modes for data confidentiality and integrity protection
US20060056623A1 (en) Block encryption method and schemes for data confidentiality and integrity protection
JPH08510365A (ja) データ暗号化のための方法および装置
WO1994021066A1 (fr) Procede et appareil pour generer un code d'authentification d'un message numerique
KR100388059B1 (ko) 비대칭키 암호 알고리즘을 이용한 데이터 암호화 시스템및 그 방법
Djordjevic Conventional Cryptography Fundamentals
Nazarov et al. An architecture model for active cyber attacks on intelligence info-communication systems: Application based on advance system encryption (AES-512) using pre-encrypted search table and pseudo-random Functions (PRFs)
Paar et al. More about block ciphers
AU683646B2 (en) A method and apparatus for generating a digital message authentication code
Handschuh et al. On the security of double and 2-key triple modes of operation
US6044488A (en) Process for generating a check word for a bit sequence for verifying the integrity and authenticity of the bit sequence
Selvi et al. A Novel Hybrid Chaotic Map–Based Proactive RSA Cryptosystem in Blockchain
AU750408B2 (en) A method of combining a serial keystream output with binary information
Krzyzanowski Computer Security
AU670355B2 (en) A method and apparatus for generating a cipher stream
Hasan Key-joined block ciphers with input-output pseudorandom shuffling applied to remotely keyed authenticated encryption
Singh et al. Encryption algorithms with emphasis on probabilistic Encryption & time stamp in network security
Rojasri et al. Secure Message Authentication Process in Mobile Computing
Hasan et al. Key-linked block ciphers with input-output shuffling applied to remotely keyed encryption
Barlow Symmetric encryption with multiple keys: techniques and applications

Legal Events

Date Code Title Description
AK Designated states

Kind code of ref document: A1

Designated state(s): AT AU BB BG BR BY CA CH CN CZ DE DK ES FI GB GE HU JP KG KP KR KZ LK LU LV MD MG MN MW NL NO NZ PL PT RO RU SD SE SI SK TJ UA US UZ VN

AL Designated countries for regional patents

Kind code of ref document: A1

Designated state(s): AT BE CH DE DK ES FR GB GR IE IT LU MC NL PT SE BF BJ CF CG CI CM GA GN ML MR NE SN TD TG

DFPE Request for preliminary examination filed prior to expiration of 19th month from priority date (pct application filed before 20040101)
121 Ep: the epo has been informed by wipo that ep was designated in this application
REG Reference to national code

Ref country code: DE

Ref legal event code: 8642

122 Ep: pct application non-entry in european phase
NENP Non-entry into the national phase

Ref country code: CA

点击 这是indexloc提供的php浏览器服务，不要输入任何密码和下载