11111111111111111111111111111111 111111111111111111111111111111111111111111
`US007167984B2
`
`(12) United States Patent
`Graveman
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 7,167,984 B2
`.Jan. 23, 2007
`
`(54)
`
`!\tETlIOI) AN)) DEVI CE FOR GENl:RATING
`APPROXIMATE i\1f:SSAC f:
`A UTHENTICATION CODES
`
`6.199.162 B1·
`6.434.699 Bl +
`(,,~~t ,OU Ht +
`
`) /2001 Luyster ...................... 71311 68
`812002 Jones 1'1 al. ................. 71311 68
`?J200~ (;mvernan
`71l/ t(,!/.
`
`(75)
`
`lnvclllor: Richard F. G ranman, Morristown. NJ
`(US)
`
`• cited by examiner
`
`(73) Assignee: "I(-!cordia Tl'chnologiu, Inc.)
`Piscataway, NJ (US)
`
`( .) NOlice:
`
`Subjcct \0 any disc!uimcr, the ICm) oflhis
`patenl is extended or <ldjusloo under 35
`U.S.C. JS4(b) by 0 days.
`
`I~rimary Hxamincr- Kambiz Zand
`(74) Allomey, Agent, or Firm- Joseph Giordano; Philip 1.
`Feig
`
`(57)
`
`AUSTRACT
`
`(21) App!. No.: 101969,518
`
`(22) Filed:
`
`Jan. 27, 2005
`
`(65)
`
`Prior Publication nata
`US 2005/0210248 A I
`
`Sep. 22, 2005
`
`Related U.S. Application Data
`
`(62) Division of application No. 09/458,336, filed on Dec.
`10, 1999, now Pal. No. 6,851 ,052.
`
`(60) Provisional applicalion No. 60/ 111 ,771 , filed on Dec.
`10, 1998.
`
`(51)
`
`Int. C I.
`1/041. 9/00
`1I04N 71/6 7
`(52) U.S. C I.
`
`(2006.01)
`(2006.01)
`713/ 168; 7131155; 7131170;
`380/229
`7131168
`(58) Field of C lassification Search
`See application file for complete search history.
`
`(56)
`
`Refe rences C ited
`
`US. PATENT rxx::UMENTS
`
`An approximate message authentication code (AMAC)
`which, I ike conventional message authentication cod(:s, pro(cid:173)
`vides nbsolute nuthenticntion of the origin of the me~~age ,
`yet provides an npproximme integrity check Jor the content
`of the message. 'lbe approximate iutegrity chL"Ck will be
`computed probabilistically and will likely be the same for
`messages hnving only a smnll percentage of differelJl bit~. A
`distance measure on the AMACs, such as a "Iamming
`distauce mcasure, may be used to detcrmine wh(.1hcr the
`number of bit dil1crcnces between the messnges is likely to
`be within an acc(.l'table amouut. 'Ibe AMAC is a probabi(cid:173)
`llstlc checksum hased on a shared key. The AMAC uses the
`message nnd n shnrcd key ns inputs. Optionally, an initial
`value may nlso be used ns nn input. In one vcNion of the
`invention, the d.1tn in the message Marc pennuted nnd
`nmmgcd (physicnlly or Jogicnlly) into n table Imving IAI bits
`in cach column and '1'2 rows, where T is may be an odd
`integer. The pcmmted data arc masked, for example, 10
`genernte an unbiased, independent, identically distributed
`set of bits (Is and Os). Taking T rows at a time, the majorilY
`bit vallie for each column is determined and that majorily
`value is used to generate a new row. This procedure is
`repeated on the T lK'W rows of majority bits. 'Ibe rL'Sulting
`IAI bits is the AMAC
`
`6 ,132.216 A • 1012000 Muntean Cl al. ............ 434/191
`
`23 Claims, 10 I)rawing Sheets
`
`, .
`
`".
`
`Page 1 of 20
`
`NETWORK-1 EXHIBIT 2003
`Google Inc. v. Network-1 Technologies, Inc.
`IPR2015-00345
`
`

`
`U.S. Patent
`
`Jan. 23, 2007
`
`Sheer I oflO
`
`US 7,167,984 B2
`
`FIG. 1
`IPRIOR ARTI
`
`,100
`
`V 102
`. . .
`
`V 102
`
`PROCESSOR
`
`PROCESSOR
`
`ViOl
`
`MAIN
`MEMORY
`
`)120
`
`V 110
`
`NElWRK
`INTERfACE
`
`V lOa
`
`lIO
`
`I-' 106
`
`DISK
`HEltORy
`
`FIG. 2
`IPRIOR ARTI
`
`202
`
`~200
`,
`
`----<.
`
`204
`
`204
`
`Page 2 of 20
`
`

`
`U.S. Patent
`
`Jan. 23, 2007
`
`Sheer 2 of]O
`
`US 7, 167,984 B2
`
`FIG. 3
`
`/
`
`,300
`
`/
`
`STAAT
`~
`SENDER GENERATES
`AMAC
`~
`(OPTIONAL) SENDER HIDES
`AHAC IN ttESSAGE AND/OR
`ENCRYPTS AMAC
`
`302 '-
`
`304 '-
`
`306 ''-
`
`30B ',-
`
`310 ',-
`
`312 '-
`
`314 '-
`
`Page 3 of 20
`
`SENDER TRANSHITS HESSAGE.
`AMAC . AND I (IF I IS
`USED) TO RECEIVER
`~
`(OPTIONAL) RECEIVER OBTAINS
`I. IF USED. AND HIDDEN AMAC
`AND/OR DECRYPTS AHAC
`
`,
`
`RECEiVER GENERA l£S AHAC
`FOR RECEIVED ttESSAGE
`~
`RECEIVER COIIPARES
`GENERATED AHAC WITH
`
`RECEIVED AHAC ,
`
`IF AHACS ARE THE SAHE.OR
`WITHIN AN ACCEPTABLE
`OISTANCE (SUCH AS A HAHHING
`DISTANCE) ACCEPTING THE
`HESSAGE. OTHERWISE
`REJECTING THE ttESSAGE
`
`,
`-,
`
`END
`
`/
`
`

`
`U.S. Patent
`
`Jan. 23,2007
`
`Sheet 3 of 10
`
`US 7,167,984 82
`
`FIG. 4A
`
`SECRET KEY K
`INITIAL VAll( I
`10PTIONAlJ
`
`HESSAGE HIOR H'J
`
`r:
`
`500
`
`PRBS
`MODULE
`
`ARRANGEMENT
`HODUlE
`6~0
`
`,400
`
`.
`PSEUDO
`RANIl07 BITS
`
`ARRANGEO
`HESJAGE
`
`PERHUTED
`HESJAGE
`
`PERMUTING
`HODULE
`)O~ OR
`)50
`
`a
`rBO
`
`MASKING
`HOOULE
`
`r 90 o
`MAJORITY
`HOOULE
`
`AHAC
`
`Page 4 of 20
`
`

`
`U.S. Patent
`
`Jan. 23, 2007
`
`Shee.4 of 10
`
`US 7,167,984 B2
`
`FIG. 48
`
`,-450
`
`/
`
`START
`
`,
`
`j
`
`414
`10PTIONAl! IF PERHUTED BY ROWS, . /
`CIRCULARLY SHIFT EACH ROW
`A RANDOH NUHBER OF PLACES . FOR
`E~LE. A RANDOH NUHBER hi IS
`CHOSEN FOR EACH OF THE i
`ROWS . EACH rowi IS CIRCUlARLY
`SHIFTED hi PLACES
`~
`MASK OR STREAK ENCRYPT V
`416
`THE PERMUTED MESSAGE.
`FOR EXAI1PLE. USE BITS
`FROH THE PSEUDO-RANlIlH
`BIT STRIN> TO BIT WISE
`XOR THE PEI'IIlJTED
`MESSAGE
`~
`41B
`FOR EACH GROOP OF T ROWS. V
`GENERA IE A tel ROW
`CONSISTING OF THE MAJORITY
`OF EACH OF THE I~
`COLUMNS . THIS YIEl T
`tel ROWS
`
`•
`
`REPEAT STEP 418 FOR
`THE T NE1I ROWS . THE
`RESULTING I~BITS ARE
`TIE C
`
`420
`. /
`
`f-
`
`/
`
`•
`
`END
`
`/
`
`402
`
`"
`
`404
`
`SENDER & RECEIVER
`AGREE ON SHARED
`lOR SECRETI KEY K
`~
`, IOPTIONAl) SENDER CHOOSES
`
`AN INITIAl. VALUE I ,
`
`406
`i ,
`
`I,
`40B
`
`),
`
`SENDER & RECEIVER
`GENERATE THE SAME
`PSEUDORANDOM BIT
`STRING. FOR EXAI1PLE.
`A PSEUDO-RANDOM
`tlIIBER GENERA TOR IS
`SEEDED WITH K AND I
`IlF I IS USED)
`~
`CHOOSE THE AHAC
`SIZE IAI
`~
`A.'IlIJI>E THE )(SSAGE
`H IDAH' 1 INTO T2
`ROWS OF IA BITS. THE ,
`HESSAGE IS PAOOED WITH os IF
`IHDED, IT .S PREFERABLY ADDI
`
`412
`~,
`
`•
`
`USE THE PSElIlO-RANODH
`BIT STRING TO PERHUTE THE
`HESSAGE. SUCH AS
`ROW-BY-ROW OR BIT-
`BY -BIT
`
`Page 5 of 20
`
`

`
`U.S. Patent
`
`Jan. 23, 2007
`
`Sheet 5 of 10
`
`US 7,167,984 B2
`
`FIG. 5
`
`,-500
`
`/502
`
`SECRET
`KEY K
`1
`~-... PSEUDO-RANDOM
`PRNG
`r----- ..
`BIT STRING
`INITIAL'VALUE I
`'--____ __ ....J
`(OPTIONAL)
`
`FIG. 6
`
`,-600
`
`V 602
`
`H
`(OR H')
`
`604,
`
`Page 6 of 20
`
`

`
`U.S. Patent
`
`Jan. 23,2007
`
`Sheet 6 of 10
`
`US 7,167,984 B2
`
`FIG. 7A
`
`KEY
`
`r----..
`I --.I
`
`[,502
`
`PRNG
`
`. / 604
`
`· • •
`
`·
`
`•
`•
`
`•
`• •
`
`FIG. 78
`
`KEY
`
`r----
`1--.1
`
`502
`
`PANG
`
`604
`
`Page 7 of 20
`
`

`
`U.S. Patent
`
`Jan. 23, 2007
`
`Sheer 7 of]O
`
`US 7, 167,984 B2
`
`FIG. 8
`
`502
`
`PNRG
`
`PERHUTED DATA
`FRoH H lOR H,,--J a02
`aoo.../
`
`804
`
`FIG. 9
`
`COL.,
`
`01234567
`1 0 1 1 0 1 1 0
`
`0 1 0 1 0 1 0 0
`0 1 1 0 1 1 1 0
`
`902
`./
`
`1 1 0 1 0 0 1 1
`
`1 1 1 0 0 0 1 1
`
`,900
`
`T·5
`IAI-a
`
`HAJORITY FUNCTION
`
`904
`
`V-
`
`I 1 1 1 0 1 1 0
`
`906
`~
`
`Page 8 of 20
`
`

`
`U.S. Patent
`
`Jan. 23, 2007
`
`Sheer 8 of]O
`
`US 7,167,984 B2
`
`FIG.
`
`lOA
`
`,-1000
`
`/
`
`START
`
`DETERHINE THE LIKELIHOOD THAT DIFFERENCES
`\Illl OCCUR IN THE SAHE COLUHN OF ASSISTANCE
`OF AN S-AflJ1AY . THIS HAY BE DONE. FOR
`EXAHPLE. BY DETERHINING THE DISTRIBUTION
`FUNCTION FOR THE NUHBER OF DIFFERENCES
`d PER COLIJIIN ACROSS ALL OF THE
`COLUHNS FOR AlL INSTANCES OF THE S-AHRAY
`
`DETERHINE THE DISTRIBUTION OF HAHHING
`IIr:IGHTS It OF COLU~S IN THE TABLE
`OF PERHUTED AND HASKED DATA
`
`USING THE RESlJI.. TS FROH STEP 1004,
`DETERHINE THE PROBABILITY THAT d
`DIFFERENCES IN A GIVEN COLUHN \IlLL
`CAUSE THE HAJORITY TO CHANGE
`
`/
`
`./ 1002
`
`V 1004
`
`1006
`V
`
`USING THE RESULTS OF STEPS 1002 AND 1006, V
`IETERHINE THE EXPECTED NUHBER OF
`DIFFERENCES IN THE T -ARRAYS COII'UTED
`FOR IfSSAGE " AND IfSSAGE "'
`
`1008
`
`ESTIHATE THE DISTRIBUTION OF THE d
`OIFFEl£NCES ACIIOSS THE COLUMNS
`IF THE T~AJRI. Y
`
`./ 1010
`
`A
`
`Page 9 of 20
`
`

`
`U.S. Patent
`
`Jan. 23, 2007
`
`Sheet 9 of 10
`
`US 7,167,984 B2
`
`FIG. 108
`
`I'A .......
`" ~
`
`REPEAT STEP 1010 TO OBTAIN V 1012
`THE EXPECTED NUHBER OF PLACES
`\¥liICH THE AHAes FOR H AND H'
`WILL DIFFER
`
`L
`
`END
`
`/
`
`Page 10 of 20
`
`

`
`"U
`Q)
`<0 ro
`
`~
`
`~
`
`o -'" a
`
`FIG. 11
`,-1100
`.................................................................................................................. ..... _\4
`
`.. .. ......... ........................ -..... ........ ..... ..... ...... ... ........ .............. ..... .............. .. s, ... i- 12
`
`1101
`....................................................................... . ... )5j ...... L 10
`
`...................................................................... ·······················_,·,,· .... ·· .... ·· .. ··8
`
`...... ........ · .... · .. ·· .. · ...... ·· .. ·· ...... · .......... · .. · .. · .... ·;;I{P?:P?'/f / ..-· .................... t- 6
`
`PERCENTAGE OF
`DIFFERENT BITS
`BEMIN AHAC
`FOR H AND AHAC
`FOR H'
`
`1104
`
`4
`
`~IfSIIED
`~BEHAVIOO
`-tr- SIHUlATEO
`BEHAVIOO
`""* PROJECTED
`
`BEHAVIOO
`
`~ I
`
`I
`0.999
`
`10
`0.993
`
`0.99993
`
`0.9999
`
`0.9993
`0.9996
`PERCENT AGE OF IDENTICAl BITS BET'o£EN
`HESSAGE H AND HESSAGE H'
`
`c::
`rn
`'"C
`~ ....
`'" := ....
`
`'(cid:173)" ? .... . '" ....
`
`~
`
`~ ....
`
`'" " ~
`!l -~
`~ -~
`
`o
`
`c
`
`CfJ ..... -'" ; ....
`00 ...
`= N
`
`'10
`
`

`
`US 7, 167,984 B2
`
`M.:TIIO)) AN)) nEvICf: FOR GENERATING
`APPROXIMATE MESSAGE
`AUTIlt:NTlCATION ConES
`
`RELATED APPLICATION
`
`-Ihis application is 11 divisional applicmion o["pplicmion
`Ser. No. 09/458,336, filed Dec. 10, 1999 now U.S. Pm. No.
`6,851,052.
`This application claims the benefit of U.S. Provisiollnl
`Patent Applicat ion Ser. No. 60/ 11J ,771 entitled "Approxi(cid:173)
`mate Message Authent ication Cock-s" for Richard F. Grave(cid:173)
`man, filed on eke. 10, 1998. The contenlS of this Provisiotl.1.1
`Patent Application are incorporated herein by reference.
`
`STATEMENT OF GOVERNMENT RIGHTS
`
`'Ihis invcution was made with Uoiled Slates Government
`support under CoopCrdliyc Agr<:cmcnt No. UAALOI-96-2-
`002 awarded by the United Stales Aouy Research Labor-I-
`tory. The Uoiled Slates Govertullent has certain right~ in the
`invent ion.
`
`BACKGROUND OF THE INVENTION
`
`:10
`
`2
`determine any pre-image that hashes to that val ue. Another
`lype uf ha~h fUllclion is a cullision r~iS1<l1l1 hash fUllct iun.
`One important feature of a col1ision r'-'Sistant hash function
`is th;lt
`it is computationally intractable to generate two
`pre-images which hash 10 the same hash value. In a typical
`collision-frec, one-way hash function, a change of one bit
`between pre-images results in an expcctation that each bit of
`the hash has abom a SOOIo chance of changing. Therefore,
`even a s ingle bit differcnce results in an entirely different
`to hash value.
`A secret key is typically a large number that is known only
`to certain users, thus the term "secret." "Secret h:y" as used
`here refers to a secret kcy in a MAC or symlIletric encryp(cid:173)
`tion algoritlun (synunetric cryptosystem). In a typical sym-
`15 metric cryptosystem, thc users, for example the sender and
`the reci p ient, agree on a cryptosystem and agree on the
`secret key. In the case of a MA.C, the sender uses the srune
`secret key to gencratc the M.A.C as the recipient uses to
`verify the MAC.
`FIG. 1 is a block diagram of a typic.11 cryptography device
`100, such as may be used in a symmetric cryptosystcm or
`MAC. T he device 100 has a Olle or more processors 102
`including one or more CPUs, a main memory 104, a disk
`memory 106, an input/output device 108, and a network
`interface 110 . The dcvices 102- 110 are COIUlected to a bus
`120 which Ir<lIlsfcrs data, i.e., instructions and information,
`between each of these devices 102- 110. The processor 102
`may use instructions in the memories 104. 106 to pcrfonn
`functions on data, which data Illay be found in the memories
`30 104, 106 andlor received via the 110 108 or the network
`intcrface 110.
`For example, a plain text Jllessage Millay be input via the
`110 108 or received via the network interface 110. The plain
`text nll:ssage may then be hashed using the proc('Ssor 102
`H and key stored in somc memory (such as main mcmory 104
`or dise memory 106). ·lbe result of this hash (i.e, lhe MAC)
`may be trnnsmitted (along w ith the plain text mess..1ge M) to
`another p.any via the network interface 110 conneck-d to a
`local area network (LAN) or wide area network (WAN).
`Similarly, a MAC may be received via the network interface
`110 and verified using the processor 102 and key stored in
`some memory (such as main memory 104 or disc memory
`106) and perhaps software stored in the main memory 104
`or the disk memory 106 .
`FIG. 2 i11ustrntes a network 200 over which cryptogrnphy
`devices 100 may conununicate. Two or more cryptogrnphy
`device~ lOll, 100' may he connected to a communications
`network 202, such as a WAN which n}.1y be the Internet, a
`telephone network, or leased lines; or a LAN, such as an
`Ethernet network or a token ring network. E."lch cryptogra(cid:173)
`phy device 100 may include a modem, network interface
`card, or other network communication device 204 to send
`encrypted m'-'Ssages andlor message authentication codes
`over the communications network 202 . A cryptography
`device tOO may be a gateway to a sub-nelwork 206. That i~ ,
`the device 100 may be an interface betwecn a wide area
`network 202 and a local area (sub) network 206 (or it may
`be rul illlerface to a stornge device, e.g., a disk controller).
`In ce,rtain situations, even the slightest change in the
`mcssage is unacceptable, such as in elcclronic paymcnts or
`precise target coordinates. In such ap plications, the strict
`determination of even a one-bit change can be critical. In
`some applications, however, such as voice or imagery, this
`strict requiremell1 is not needed and not desirable for the
`reasons discussed. The message may be slightly alterx.-d after
`the sender generates the MAC. This may happen, for
`example, if the nK'Ssage is a still image (i.e., a picture) and,
`
`25
`
`I. Field of thc In\·cntio ll
`The present invention relmes to authenticating the source
`and integrity of transmined or stored information. In par(cid:173)
`ticular, the prescnt invcntion is a method and device for
`generating approximate message authenticmion codes
`(AMAC). An AMAC provides absolute all1hell1ication of the
`source or origin of a received message and pennits verifying
`approximatc integrity between the origiillll mess..1ge and the
`receiv,-'(]. message.
`2. Discussion of Rclated An
`It is often desirable to ensure that the SaUTee or origin of
`a message or other communicat ion is who it is represented
`as being and that the receivL><i message is the same as the
`original mess..1ge. One well-known way to provide this type
`o f authent ication is a Message Authentication Code (MAC). 40
`A MAC is generated for an original message M and is sent
`with the message. This al lows the recipient of a message to
`verify that the received message M' was acnmlly sent from
`the purported sender and that the mess..1ge has not been
`altered from the originally transmitted message M. This can 45
`be done by the message sender applying 11 one-way hash
`function (d,-'Scribed below) on a S(."CTCt key (:tlso described
`below) and the message M. The result is a MAC. The
`recipient may receive the message M' and the MAC. If the
`recipient has the secret key, she can then apply the same hash 50
`functio n to the key and message M'. If the two MAC values
`are the same, the messages arc identical. Because the secret
`key correctly computed the MAC to obtain the hLlSh value,
`the message origin<1ted from the purported sender. Because
`the MAC values nrc the snme, the rx."Cipient hus ulso verified 55
`that the rx.-ceived message M' has not been alteJ\.'(]. from the
`original message M.
`A hash function is a function which takes an input string
`of any length (often ca11ed a pre-image) and computes a
`fixed-length omput string (often called a hash value). In thc 00
`example above, the pre-image is the original message M. A
`one-way hash function is a hash fUllction for which it is
`computationally intractable to find two pre-images with the
`same hash value. Briefly, a one-way function is a function
`that is easy to compute but hard to inven o n :m overwhclm- 65
`ing fraction of its range. In a good one-way Iwsh function ,
`givcn a hash value, it
`is computational1y infe:lsible to
`Page 12 of 20
`
`

`
`US 7, 167,984 B2
`
`4
`'Inc AMAC is a probabilistic checksum baS(.--d ou a shared
`key. The AMAC us~ the mes:;.;Jgc ,mu 1I sham.! k(."), us
`inputs. Optionally, an initial randomizing val ue may also be
`used as <In input, as well. In a preferr(.x\ embodiment, the data
`in the message M are pennuted and arranged (physically or
`logically) into a table havillg IAI bits (the number of bits of
`the desired AMAC) in each column and T2 rows, where T is
`prefernbly an odd illleger. The pemllited data ure masked, for
`example, by exclusive-ORing with pseudo-rnudom bits, to
`genernte an unbiased, independent, identically distributed
`set ofbils. Taking T rows at a time, the majority bit value for
`each column is detemlincd and that majority vu llie is uSL--d to
`generate a n(."W row. This majority calculation repeated on
`the COIUlllllS of the T new rows of majority bits. The resulting
`IAI bits is the AM AC.
`·Ine recipient receives a message M' and an AMAC for the
`original message M from a purported sender. The recipient
`uses the key it shares with the purported sender (and perhaps
`an initial value) to generate an AMAC for the r<."Ceived
`message M'. If the key is different from the one us(.x\ to
`genernte the original AMAC, the AMAC generated by the
`recipient will be entirely different from the AMAC from the
`sender a nd the message will be rejected because the sender
`is an imposter. If the AMAC values are the same, (I) the
`sender is who he purports to be and (2) the bit diflerences
`between the original message M ilnd rcceived message M'
`are witltin rul acceptable threshold. An even greater thresh~
`old of bit dillerenc(.'S may be acceptable and a measuTC, such
`as a I·lamming distance measure, may be used to de temline
`if the number of bit differences betwccu AMACs is accept(cid:173)
`uble, such as whether the llumber of bit di flcrenccs do not
`excccd 1:1 predetemlined expected uumber of bit dillcrences
`between the messages.
`·Ine acceptable number of bit differences betw(:en mes(cid:173)
`sages may be represented by the number o f bit differences
`between the AMAC for the original M and the AMAC for
`the received message M'.
`
`BRIEF DESCRIPTION OF T HE DR.AWINGS
`
`I S
`
`3
`after the hash value is gcncr<ll(.:d, "hidden text" is ;ldued to
`the imilgc. l'liddcn lext Ul<ly be !I "digilill willcnllilrk" or
`"fingerprint" added to an image to identify tIle origin orlhe
`image. A content provider may include hidden data on ;m
`image it posts on the Interne!. The hidden dma may be used
`as evidence of ownership and copying if another party
`image. Although the hidden dma
`misappropriates the
`involves no illicit " tampering" Ihm should cause the recipi(cid:173)
`ent 10 rcjccl Ihe image, some of the information lILts been
`changed. lliis change causes the hash value of the received 10
`message M' (which contains the hidden d<lta) 10 be entirely
`diflcrcnl from the hash va lue of the original message M
`(which docs not contain the hidden data). This leads the
`recipient to conclude thm the received message M' has been
`forged or ahered and is unreliable. The same problem arises
`for images and voice if noise is illlroduced il1l0 the message
`during transmission.
`"Lossy compression" is another applicmion where infor(cid:173)
`mation may be lost or ahen:d in a way tlILtt should be
`acceptable. For example, a still image (a picture) may be :10
`compressed llsing a lossy compression tecllllique such as
`JPEG after the MAC is generated. JPEG is a data compr<.'"S(cid:173)
`sion technique that el iminates rc::dlmdant information from a
`still image. As a result, some of the infonnation in the
`original image (message M) may be lost when it is com- 25
`pressed and later decompressc::d. Ncvertheless, the changcs
`in the received message (decompressed inwge M) arc not
`illicit tampering., nor is the image a forgery. Therefore, this
`comprl-'Ssed-<lecompressOO image M' should have sufficient
`integrity to be accepted. However, because there has been 30
`some changc in thc data, a MAC using a Imsh function will
`show that the integrity of the image has been compromised,
`and the image will be rejected.
`"Ihere is a nced to provide a mL'Ssage authentication code
`thm penllits abwlute authentication (Le., the sender is the H
`party identified as the purported scnder) ulld approximute
`integrity (i.e., the message has undergone no more thun
`some acceptable lUuount of modificution). For example, the
`rccipielll should be able to determine thm the diflcrences
`between the original message M and the received message 40
`M' are only slight. 'i11is permits some integrity loss due to
`hiddcll (\.1ta, noise, some instances of lossy compression, or
`other change, but prevelllS all OUi forgeries, substalllial
`changes in coutent, or "Cllt-and-paste"' attacks.
`Therefore, it is an object of the present invelllion to 45
`provide a method and device for genernting an approximate
`me~sage authentication code which pmvidL'S ;th~lute
`authentication and approximate integrity.
`It is another object of the present invemion to provide a
`method and device w hieh pemlits a recipient to aecept 50
`certain IlK'Ssages as authent ic and sufticiently unaltered,
`even if there is a slight c.hunge in the message.
`
`nle present invention is described with refcrence to thc
`following figur(.'S:
`FIG. I is a block diagrnm of a typical cryptogrnphy
`device;
`FIG. 2 is a simplified diagram illustrating a network over
`which cryptography devices may conununicate;
`FIG. 3 is a flowchan of an overview of Ihc mcthod
`according to the pr(.'Sent invention;
`FIG. 4A is a block diagram of au AMAC generntion
`device aceording to the present invention;
`FIG. 4 13 is a flowchart describiug a method for genernting
`itnAMAC j
`FIG. 5 is a block diagrdm illustratiug a pseudo-random
`55 bit-string generator module:
`FIG. 6 is a block diagram illustrating an arrangement
`module of the invention which arra nges the message M (or
`M') into a table of dimension IAI by T2;
`FIG. 7A is a block diagram illustrating a fin;t embodiment
`00 of a pemlliting module of the invention which permutes the
`message M (or M') by row;
`FIG. 7 B is a block diagram illustrating it second embodi(cid:173)
`ment of a pennUling module of the invention which per(cid:173)
`mutes the message M (or M') by bit;
`FIG. 8 is a block diagram illustrating a masking module
`of the invention which masks or strc.1m encrypts the per(cid:173)
`muted message;
`
`S UMMARY OF THE INVENTION
`
`invention arc
`'lhe!;C and other objlXts of the pr<.'"Sent
`provided by an approximate message authentication code
`(AMAC) which, like conventional message authenticmion
`codes, provides absolu te au thentication of the origin of the
`message, yet provides an approximate integrity check for the
`content of the message. The approximate integrity check is
`computed probabilistically and will likely be the same for
`messages having only a small pereentage of diflerem bits. A
`distance meusure on the AMACs, such as a Hruruning
`distance Illeasure, may be us(:d to measure whether the 65
`number of bit differences bctw(:en the messages is within a
`predetermined acc(.-pt.1ble amount.
`Page 13 of 20
`
`

`
`US 7, 167,984 B2
`
`5
`FIG. 9 is a block diagrnm showing sample values of a
`simpli lktl majority module whkh oc\cnnim.:s lhe lIwjurilY
`bit value for the columns of an arrJY;
`FIGS. IO Aund lOB nre II tlowclmrt illustruling the method
`for calculating thc cxpccll'd d illcrcnccs in the AMACs.
`given a certain Hrunming dis\lIllcc between message M anci
`message M'; and
`FIG. I I is a graph illustrating the desired behavior. the
`predicled behavior, and th.e simulated behavior of an AMAC
`
`DETAILED DESCRIPTION OF PREFERRED
`EMBODIMENTS
`
`6
`not the messages may be considered "close enough" for the
`pilTli{;ulur ilppli{;tltion. For cxalllpk. fur somc ilppli{;iltioll, it
`may be acc<.-ptable to have a difference in the messagl'S M,
`M' of as many as one diflcn.'llt bit per S()()() (i.e., 0.02%).
`This percent differcnce is likely to result in a slllall Ham(cid:173)
`ming distance between AMACs. Dillcreuces between m<.'S(cid:173)
`sages M. M' having a distance measure cqual to or less than
`that amount will pennit the received message M' to be
`:Leccptcd with high probabi lity and having 3 distance mea-
`to sure greater than that amount wi ll rt.'Sult in message M' being
`rejl'Cll'd with high probability (stl-P 314).
`
`Overview of the Invention
`FIG. 3 is a flowchart .100 of lm overview of the method
`according to the present invention. A sender generates an
`Approximate Mcssllge Authentication Code (AMAC) for a
`mt.-ssagc M where approximate imcgrity is acc(.1'tabJc (step
`302). Some examples of messages where approxim.11C integ(cid:173)
`rity may be aeceptable include a still or moving image or
`voice. A pcrsoll skilled in the art readily recognizes that
`many types of messages may fall within this cmcgory. '11le
`AMAC may be gencrau..-d usillg a shared (or secret) key
`shan.-d with the illtl'nded n.'Cipient and, optionally, all initi.11
`value I. Optionally, the sender may hide the AMAC in the
`message M, using for example, steganographic 1(.'(;hniqucsj
`the AMAC nMy be encrypted; or the AMAC and nK'Ssage
`may be combined (for example, possibi lities include con(cid:173)
`catenation or steganographic techniques) and the eombin.1-
`tion encrypted (stcp 304). These steps may be pcrfonm .. 'd by
`a cryptography device l OO (as seen in FIG. l ), spL'Cial
`purpose processor, or computcc.
`The scoder may tlK'n trnnsmit the mesS;:lge M, Af-t<\C,
`lind, if nsed, an initial value I (oc'Scribcd below) (stcp 306). Jj
`This transmission may be made via the network communi(cid:173)
`cation device 204 (seen in FIG. 2) ovcr a local area IICtwork
`(LAN), wide area network (WAN) such as the Internet, or
`othcr transmission or storagc medium. 'Ibe transmission of
`the message and the AMAC may bc OYcr H noisy channel. If 40
`an inilial value I is used, it should be tr:.msmilll'd oyer :!
`reliable ChaJUlCI, slIch as in an out-of-band chmUlel or IIsing
`an error correction cexle. The tr:Lnsmission of step 306 Illay
`also be made to a storage medium. such as main Illemory
`104 or disk memory 106 (s<.'Cn in FIG. 1) for later retrie1{"",tl 4S
`or other use,
`The recipiClit receives (or retrie\'es) thc messagc, AMAr.
`and (if nsed) the initial value I and obtains the message M'
`and the AM<\C (stcp308) by JX!r.sing the d1ta, decrypting the
`AMAC and/or the message M', or other appropriate ml1hod. SO
`'Ibe recipient then generntes another AMAC (step 310)
`using t he message M', the sh.1I\."(\ key, and initial valuc I, if
`uS\.'(). B<.'Cause the ~ urit)l of theA MAC dl-pends on Ihe key
`nnd I (ifused), the AMAC iscompull'() probabilistically, and
`11 chunse in the message mayor may not change the AMAC, 55
`dt-pcnding on the key and I. '11K! AMAC gener.lled from the
`received message M' is compaR"<i with the AMAC of the
`original message M (step J I1).lfthe messages M, M' are thc
`sanK!. o r if only a sm.all percentage o f bits arc different ( for
`examplc. if 0.005% to 0.0 1% bits lIIe different) thcy may 60
`have the same AM.<\C value and the received mess.1gc M' is
`:Icceph,.'d as having sullicicll\ integrity. (Also, because the
`AMAC is similar, the shart.'d key K and, if used, I were
`eorn.'Ct and therefore the sender is authenticated as who he
`purports 10 be.) If the mcss..1gl'S M, M' have a gn.>(lter 6S
`percentage of dillcrent bits, a di stance me;!sure (sllch as a
`l'lamming distance) may be uS<."<i to detenlline whether or
`Page 14 of 20
`
`15
`
`GCIK'rnting An Approximate Message Authentication Code
`FIG. 4 A is a block diagram o fa preferred embodimcnt of
`lIll AMAC genenltion device 400 :!ccording to the present
`invention. lbis AMAC generation device Illay be imple(cid:173)
`mcnted, lor eXlUllple, in a cryptogmphy device 100 such as
`is S(.'Cn in FIG. I , in a special purpose computer, an :!ppli(cid:173)
`cation specific integrJIl'() circuit (ASIC), or suftware run-
`20 ning on a conventional computer. As seen in FIG. 4A. a
`secret (or shared) key K and, optionally. an initial valuc I arc
`input into a pseudo-random bit string (PRBS) generator
`module 500. TIle PROS generator module 500 OUlpUts a
`pseudo-random bit string, 1bc mcss..1ge M (or M') is inplll
`25 into an a rrangement module 600, which outputs the mCSS.1ge
`llrrangcd a particular way. The arrangl'<l message and rnu(cid:173)
`dom bits from the PROS are input into a pennuting module
`700 or 750, which pemllltcs dall! in the arr.m gcd message.
`The permuted data arc input into a rna.king module HOD
`30 which masks thc pcmlllled dllln. 'Ibe masked data arc sent to
`a majority modulc 900, which copics the masked da!.1 into
`cl ..... ain arrays (called S-arr..!ys) and dl'lennines the majority
`bit value in each column o f each array. The majority bit
`values or each S-array arc placed in another array (called a
`T-army). The majority modulc detennincs the majoril)' bit
`value in each colwnn of the T-arrny. 'Ibe result o flhis second
`proct.'Ss is the AMAC.
`FIG. 40 is a nowchart 450 describing the method for
`generJting an AMAC. l bc sender and receiver agree on a
`shan.'<I o r secret key K (step 402). 'Ille sharl'<l key K may be,
`for example. computed using a Di llie-Hellman key
`exchangc, but any conventionnl IlK'Ihod of choosing a
`shared key may be used. For examplc. the sCllder and tlK'
`recipient may authenticate cach OtlWf. genemte the shared
`k<.")' K, use the key, and discard it. lltis permits only
`"on-line" auacks. The length o f key K is not important 10 the
`invention. but the key is preferably long enough to pre"cnt
`it from being guessed by trying a ll possible keys. A 96-bit
`key is satisfactory for current technology, but in the flllure,
`longcr keys may be desirJblc.
`Both thc sender and the rt.'Cipit'llt also have the samc
`pscudo-random bit string generator module 500, and which
`prefcrJbly includ<.'S 1I eryptogmphiclllly strong pseudo-r:.u!-
`dom number gcnerntor (CSPRNG). Any standard. olT-thc(cid:173)
`shelf PRNG or CSPRNG may be USl"<i. '111e (CS)PRNG may
`be softwHre running on a processor. such as pmc<.'Ssor J 02
`secn in FIG. I. For example. the CSPRNG may be the key
`stream generator for a stream ciplK'r. such as RC4 (owned by
`RSA Data Security, Inc, Redwood City. Cal if.) or VRA
`(owned by Telcordia Technologies). Note thallhe same input
`into these two (CS)PRNGs w ill R'Sult in the same OUlpln.
`lbe outp ut of the (CS)PRNG is a pscudo-random bit string
`(PROS). lbis will be lIsed to genemte approximatcly as
`nWlly bits as the total size of the mt-ssage bl.>ing allihenti(cid:173)
`c3wd.
`OptiotL:!lly, an initilll va luc (or initial wetor) I is chosen
`(stcp 404). The initial value I need not be kept secret. For a
`
`

`
`US 7, 167,984 B2
`
`7
`given key K and mcssage M, [he sender Cim produce a
`nllllily of AMAC~ pardlllclcrizl-tl by the inili1:l1 v<lluc L I may
`be arbitrarily choscn and is prcfcTdhly the output of an
`incremental counter or 11 clock. Varying the initial value
`makes .macks on the AMA.C more difficult and permits
`many uses of the shared key K. Each initial value I defUlcs
`differem neighborhoods, i.e., defines a different pnnilion of
`messages into ones with the salllcAMAC. The selccted I and
`the shared key K affect the ca1cubtion of the AMAC
`probabilistically.
`'Ihe sender and receiver generale the same pseudo-ran(cid:173)
`dom bit slrillg (siep 406). As seen in FIG. 5, ;t pseudo(cid:173)
`random bit SIring gelleTdlo r module 500 lll<ly be lIsed by both
`the sender and receiver by seeding the (CS)PRNG 502 with
`shared key K <Iud, if used, init ial value L Because the
`identical inputs are uscd in the same (CS)PRNG, the pseudo(cid:173)
`random bit strings that are output will be identic,,!' Note thm
`the sender "nd receivcr can pcrfoml this step in "dv"nce
`once they both have K (and I if uS(,.,(]). Each could gener.tle
`the pseudo-rnndom bit stnng (PROS) at any time before or
`during thc gcneration of their respective AMACs.
`Returniug to FIG. 48 , the size of theA MAC IAI is chosen
`(sK1I 408). lbe size of the AMAC IAI is the number of bits
`long the AM.!\ C will be. As discussed below, the selection of
`IAI "flects the AM..A..C's sensitivity to bit differences. The
`AMAC should be kmg enough to make it prohibitively
`unlikcly th"t "n att"cker can guess "n "ccept<lble v"luc for"
`forged message. SO it wi ll typically beat least 100 bits long.
`The upper bound for the length of the AMAC is dictated by
`convenience, so that IAI is usu"lIy chosen to be I 00 to 300
`bits. Once