An Attempt to Cancel Patent For Breaking GSM Standard Algorithm

GSM logoDr Elad Barkan invented or discovered a cryptology method for breaking GSM coded communications and filed a patent application on 30 April 2003 titled “Cryptanalysis Method and System”, which was awarded Israel Patent No. IL 155671 in June 2005. The method was based on the discovery of a fundamental coding flaw in the GSM protocol which caused quite a stir among both telecommunication experts and the cryptology community.

DiscoveryOn 23 June 2015, Rontal Engineering Applications 2001 Ltd applied to have the patent cancelled on various grounds including that it was a discovery and not an invention; that the supplementary tests of inventiveness were met so that there was no inventive step, and that the patent was never implemented. In a long and detailed decision, Deputy Commissioner Ms Jacqueline Bracha considered the various allegations and ruled on the validity of the patent registration.

After the statements of case and the evidence were submitted, a three-day hearing was scheduled in December 2016, and the parties then submitted written summations.

Complicating matters, during the summation stage, the Opposer, Rontal Engineering Applications 2000 Ltd, filed for bankruptcy. Dr Barkan submitted a request that Rontal Engineering post a bond for 200,000 Shekels, to pay his legal fees should he prevail against them. The Deputy Commissioner agreed with his request and a bond was posted duly on 15 July 2017.

Somewhat unusually, the ruling starts with a list of definitions of various words relating to the GSM protocol. Then the decision goes on to rule if the invention relates to patentable subject matter.  In a 46 page ruling with 165 paragraphs, the Deputy Commissioner found that the invention is patentable per se. Furthermore, the invention described is substantially different to the closest prior art so the patent was upheld.

In my conclusions at the end of this article, I conclude that the Opposers could probably have successfully obtained their real objective by negotiating a claim restriction to exclude brute force attacks which were never intended to be covered by the claims anyway.

A summary of the Decision follows.

Glossary

The patent relates to GSM encryption, and to understand the case, a number of terms need to be defined.

GSM NETWORKGSM is an acronym for Global System for Mobile Communications. It is a standard for cellular phone networks developed in 1987 and available since 1992. The standard was published before the priority date. The standard is a digital telecommunication standard and voice is digitized, transmitted and then converted back into sound. GSM is encrypted to prevent third parties from eavesdropping. The communication takes place via base stations.

GSM SIMEach user has a SIM (Subscriber Identification Module) card installed in their mobile phone. Each SIM has an associated unique IMSI (International Mobile Subscriber Identity). When a specific mobile phone wishes to connect to a mobile network, it sends the IMSI to the base station. The base station accepting the call refers the IMSI to a database in the base station in order to relate the IMSI of the mobile phone with a dedicated private key Ki that is saved in both the SIM and in the database of the base station. As a result of this association, the base station sends a random number RAND to the mobile phone, and on receipt of the RAND, the mobile phone generates a signed response SRES which is sent back to the base station. The SRES uses the Ki with the RAND received from the base station. The SRES is generated by the mobile phone when the key Ki and the random number RAND are both fed into an A3 encryption algorithm. The base station does the same action to create the SRES, and after receiving the SRES from the subscriber, it compares the two numbers. If the two numbers are identical, the subscriber is connected to the network. However, if they are not identical, the phone is disconnected. These actions are performed before the phone is connected to the network, to ensure that the subscriber itself and not a fake subscriber is connecting.

At the next stage, the subscriber and the base station generate a specific encryption key for the conversation that is known as a session key or a conversation key Kc. The GSM protocol uses 64 bits where 10 are known and predetermined. The encryption key is independently generated by both the base station and the mobile phone, using the RAND and the Ki, where both are encrypted using an A8 encrypter.

frameThe digital data transmitted in accordance with the GSM protocol is divided into frames that are 114 bits long. Each frame is transmitted in a 4.6 millisecond time slot. The frames are all encrypted with the conversation key Kc and with the frame number fed in with an A5 algorithm that produces a keystream that is also 114 bits. To encrypt all the frames, the keystream is transmitted together with the exclusive or XOR information. The result of this action is known as ciphertext. The process that couples the keystream with the frames before encryption is known as the stream cipher.

keyThe base station calculates the keystream using the conversation key Kc, the number of frames and the A5 algorithm that is used for encryption, and this is also used to decode the frames of information. In the GSM standard, the same A5 algorithm serves for generating the keystream and for coupling the mobile phone to the network (the uplink) and for coupling the network to the mobile phone (the downlink).

secretThe A5 algorithm includes two main algorithms: A5/1 and A5/2. The A5/1 algorithm is the more difficult to crack. In 1999 both the A5/1 and A5/2 algorithms were reverse- engineered and published. However, knowing the structure of the algorithms is not sufficient to break them. It will be recalled that the keystream is created by combining the conversation key Kc with the frames, but the conversation key Kc remains secret. So that the conversation key Kc remains secret, it is not transmitted between the mobile phone and the network. The GSM protocol includes a cryptography protocol that enables the mobile phone and the network to separately create the identical conversation key Kc that is only known to them, thereby eliminating the need to transmit the conversation key Kc over the airwaves.

secret messageIn the GSM protocol, the message includes the digital information (such as the voice signal of the conversation) and also includes control signals and a code for detecting and correcting errors (ECC). All the information including the content is encrypted before being transmitted.

In GSM, the communication between the mobile phone and the base station uses radio waves which are noisy communication channels. The GSM standard includes a code for addressing ansd correcting errors and for generating the original error free code. This is known as the Error Detection Code ERR. It works by adding a known number to the bits of each message which is sufficient for the receiving station to identify and fix a small number of errors.

errorThe GSM standard uses an Error Detection Code ERR of the convolutional encoding type. The GSM standard uses non-systemic encoding, meaning that it is not enough to add many bits to a message, but the original bits are also transformed.

RedundancyRedundancy is the external information that has relevance to the message prior to encryption. The external information includes the language of the conversation, the communication standard (In this instance, the GSM standard), knowledge of the protocol structure for the communication standard, knowledge of the probability that one or another message will appear at some stage of the protocol, open information that an attacker can obtain from public sources, such as the GSM standard documentation, and the like.

cryptCryptanalysis is the branch of Cryptology that deals with analyzing data systems to expose the encrypted/protected/hidden elements. The purpose of the cryptanalysis is to break the encryption defenses of encrypted systems to expose the content.

Plaintext is the information of a notice prior to encryption.

Ciphertext is the information of a notice, after encryption.

To free the encrypted text to its unencrypted version, i.e. regular text, one has to attack the encrypted system to reveal the encrypted test and in many instances, to uncover the key that translated the encrypted text back into regular text.

attackActive Attack and Passive Attack

Active attack involves the attacker sending radio signals that interfere with the network in a manner that serves the attacker’s interest. Passive attack is a form of attack wherein the attacker does not actively send signals or disrupt the communication, but merely listens in to the communication.

There are a number of cryptographic attacks. Those of interest to this decision are:

  • Ciphertext only attack wherein the attackers expose the plain text of the key by using the encoded text only
  • Known plaintext attack wherein the attackers have a quantity of encoded test and non-encoded text

The difference between ciphertext only attack and known plaintext attack is that in ciphertext only attack, use is made of redundancies, i.e. external information that is not the plaintext message, in order to access the plain text message itself, without needing to know the content of the message. In known plaintext attack, the message itself is also used, and not just the redundancies.

  • Brute Force Attack – this is an attack that systematically attempts all possible keys in turn on the encoded message, until the right key is selected. This generally requires time and computing power
  • Downgrade attack / roll-back attack – this is a type of attack wherein the attacker acts positively so that the mobile phone or the network select a weaker encryption than they would otherwise select
  • Man-In-The-Middle Attack – this is an attack wherein the attacker mimics the mobile phone to the network and the network to the mobile phone, whilst encrypting the content as would a legitimate customer

The Claimed Invention

cryptThe claimed invention is a “Cryptanalysis Method and System”. The invention deals with code breaking by using the ciphertext only to break the A5/1 and A5/2 algorithms that are used to encode the information that is transmitted on the cellular networks in accordance with the GSM standard. The invention enables breaking into and listening to communications on the network.
The patent has 37 claims of which claims 1 and 4 are independent. Claim 1 recites:

“A cryptanalysis method comprising:

  1. Performing a ciphertext-only direct cryptanalysis of A5/1;
  2. Using results of step (A) to facilitate the decryption and/or encryption of further communications that are consistent with encryption using the session key and/or decryption using the session key.”

Claim 4 states:

“A cryptanalysis method comprising:

  1. Performing a ciphertext-only direct cryptanalysis of A5/2;
  2. Using results of step (A) to facilitate the decryption and/or encryption of further communications that are consistent with encryption using the session key and/or decryption using the session key.”

There is no argument that the inventor discovered a way of breaking the encryption that utilizes the fact that the GSM encryption protocol uses the code for error correction prior to encoding. As explained in the Application, the error correction is performed prior to encryption such that the original message prior to its encryption is that which is extended by the code, and not the message after encryption. The error correction code used in establishing a message is the known SACCHI code (page 15 of the patent).  Consequently, the encoded message includes high level redundancies that are created by the error correction code, which reveal a lot of information about the keystream. These redundancies influence all the other redundancies that may exist in the communication. The reason for this is that all channels undergo an error correction stage prior to encryption, so all redundancies in the channel will undergo the correction and will be widened by the redundancies that the code adds prior to encryption.

keyOnce the system knows about the keystream, one can recreate the conversation key Kc, or to decode or encode additional messages by conventional cryptanalytic attack, without revealing the conversation key Kc. The patentee claims that from the moment that the conversation key Kc is revealed, one can use it to code or decode all the messages.

The patent also describes that the protocol that creates the conversation key Kc in the GSM standard is attackable since it does not create a different key that depends on the encryption algorithm chosen by the network. And does not distinguish between the up-link from the user to the base station and the down-link from the base-station to the user. The inventor claims that the result of this is that all the versions of the A5 algorithm share the same key that is agreed to by the algorithm for both uplink and downlink communication. So in all versions the conversation key Kc will always be identical for the same subscriber and the same RAND random number.

The Parties’ Evidence

The Applicant for Cancellation submitted an Opinion by Professor Amir Herzberg. The patentee submitted an Affidavit by himself, and a further one from Professor Eli Biham, his co-inventor, and an opinion by Professor Dani Dolev. The Applicant for Cancellation then submitted an Opinion by Attorney and Patent Attorney Stanford T Colb and one by an expert whose identity is covered by a secrecy order (see earlier interim decision of 18 August 2016).

In a decision of 18 September 2016, the Deputy Commissioner rejected a request by the patentee to strike Adv. Colb’s Opinion, but let him respond. Paragraphs 409 of the non-identified expert were also struck from the record.

On 15 November 2016, Dr Parkan submitted an Affidavit as counter-evidence to Colb’s opinion, and on 24 November 2016, the Applicant for Cancellation submitted a request for this Affidavit to be struck, which was agreed to in a further interim decision of 19 December 2016.

In the first and second Opinions, the Expert related to basic terminology of the field as an explanation of the claims and as questioning the novelty, and the following publications were appended to the Opinions.

  • Diffie and M. E. Hellman, Exhaustive Cryptanalysis of the NBS Data Encryption Standard”, Computer, pp. 74-84 (1977) (“Diffie I”);
  • Diffie and M. E. Hellman, Privacy and Authentication: An Introduction to Cryptography”Proceedings of the IEEE, Vol. 67 (3), pp. 397-427 (1979) (“Diffie II”);
  • D. Golic, Cryptanalysis of Alleged A5 Stream Cipher, in Advances in Cryptology – EUROCRYPT ’97, Lecture Notes in Computer Science 1233, W. Fumy (ed.), Berlin: Springer-Verlag, pp. 239-255 (1997) (“Golic”);
  • “The (Real-Time) Cryptanalysis of A5/2” (presented by Nikita Borisov, 26.8.1999) (“Borisov”);
  •  Pesonen, Helsinki University of Technology,GSM Interception (21.11.1999) (“Pesonen”);
  • 3GPP TSG SA WG3 Security — S3#14 S3-000466 1-4 (August, 2000) (“3GPP 2000”); 
  • 3GPP TS01 V7.2.0 (2001-11) (“3GPP 2001”);
  • Biryukov, A. Shamir and D. Wagner, Real Time Cryptanalysis of A5/1 on a PC, volume 1978 of Lecture Notes in Computer Science, pages 37–44. Springer–Verlag, pp. 1-18 (2001) (“Biryukov”);
  • K. Lenstraand E. R. Verheul, Selecting Cryptographic Key Sizes”, Journal of Cryptology, Vol. 14(9), pp. 255-293 (2001) (“Lenstra”);
  • Boman, G. Horn, P. Howard and V. Niemi, UMTS Security, Electronics & Communication Engineering Journal, Vol. 14(5), pp. 191-204 (2002) (“Boman”).

In his expert Opinion, Professor Dolev related to things discussed in Professor Herzberg’s opinion, and appended the following publications:

  • Ross Anderson, “Security Engineering – A Guide to Building Dependable Distributed Systems”, 2nd, (September2010) (“Anderson”);
  • Christophe Guillemin, Cracking the GSM Encryption Protocol, ZDNet (17.9.2003) (“ZDNet”);

Professor Biham related to the response by the academic community to the invention, and attached the paper that was the basis of the patent:

  • Barkan, E. Biham and N. Keller, Instant Ciphertext-only Cryptanalysis of GSM Encrypted Communication, In: Boneh D. (eds) Advances in Cryptology – CRYPTO 2003. CRYPTO 2003. Lecture Notes in Computer Science, vol. 2729. Springer, Berlin, Heidelberg (2003) (“Barkan 2003”).

Adv. Colb compared the scope of the corresponding US patents with that of the present application. The corresponding US patents are:

  • US 8,009,826
  • US 8,295,477
  • US 9,038,192

RULING

Section 73b of the Israel Patent Law 1967 states that:

At the request of a third-party, the Commissioner is authorized to cancel a patent if he considers that there is reason that it should not have been granted.

The burden of proof lies with the Applicant for Cancellation as stated in 8802/06 Unipharm vs. Smithkline Beecham PLC, from 18 May 2011:

Section 37 of the Law complements the idea that “examination and issue of a patent are no guarantee that the patent is enforceable”. So the issuing of a patent by the Commissioner is not unassailable evidence of its validity. All it teaches is that the Commissioner thought it should have been granted. Appeal 47/87 Hasam Maarachot (Blocking Systems) Reliable Defence Ltd.  vs. Bachri, p.d. 45(4) 194, 201-202 (1991). However the burden of proof is on the shoulders of the requester for cancellation (Appeal 665/84 Sanofi vs. Unipharm Ltd, p.d. 41(4) 729, 736 (1987), Appeal 700/78 Issesco International Solar Energy Company Ltd. vs Banit, p.d. 34(1) 757, 763, (1979).

See also Cancellation Ruling for Comperless Ltd. vs. Mobidum Ltd., 19 August 2008 paragraph 38, Cancellation Ruling 148492 “Mishkan Tchelet (Indigo Tabernacle) Industries vs. “Keter” (Crown) Ritual Items Ltd, 8 March 2009, paragraph 54 and Cancellation proceeding 157035 Tzachi Oz Airconditioning vs. Moshe Lavie et al., 5 March 2017.

The basis for a patent cancellation request is essentially the reason for which the patent application can be opposed, and the justifications are listed in section 31 of the Law. Of these, the most common reasons are lack of Novelty, lack of Inventive Step, greedy claiming and lack of clarity of the claims.

Is this an invention?

inventionThe Applicant for Cancellation alleged that the claimed invention is merely a diagnosis and not an invention. The Applicant for Cancellation admits that there are two main diagnoses:

  • The fact that the GSM Standard includes a code for correcting mistakes that is applied before encryption
  • The fact that in the GSM Standard, the conversation key Kc will always be identical, regardless of whether the A5/1 or A5/2 algorithm is used, so long as the same RAND is used.

However, the Applicant for Cancellation does not consider these diagnoses of the GSM Standard as being an invention whereas the patentee claims that the invention is using these diagnoses to crack the encryption. In other words, the issue is whether this is an invention or a discovery of something inherent in a known system.

In 804/89 Lenplast (1971) vs. Eliezer (Leizer) Brekman, p.b. 46,(2) 295, it was stated that a discovery will be considered as being a patentable invention if it is accompanied by a practical application that results in a product, process, result or new combination. On page 35:

The point of departure is that a discovery in and of itself is not protectable as a patent. For a specific discovery to be considered as being an invention, it is necessary for it to be accompanied by a suggestion for something practical which can be done, and which leads to the result of a new product, process, result or new combination… In this case we can state that it is insufficient that the respondent discovered that a known board, previously used for writing, has optical properties, surprising though they may be. To translate this into a device that is patentable, it is necessary to reveal something secial that leads to a new process or new device, etc.

Terrel, in “Terrell on the Law of Patents, 17th ed., [2011]”, page 30 states that one cannot obtain a patent for a discovery. However, one can patent a use of the discovery for obtaining a product, process or application.

“Discovery adds to the amount of human knowledge, but it does so only … by disclosing something … Invention also adds to human  knowledge, but not merely by disclosing something. Invention necessarily involves also the suggestion of an act to be done, and it must be an act which results in a new product, or a new result, or a new process, or a new combination for producing an old product or an old result“.”

In fact, there is no disagreement between the parties that the fact that the Error Detection Code ERR of the GSM Standard was applied before the priority date (see the 3GPP 2001 publication in Appendix), however the inventors did not merely point to this property, but also suggested a use for it to attack the system. In other words, they recognized that the properties are a security weakness and a point of penetration. So we are not referring to a discovery per se. but to a practical application of a property of the system. Therefore the assertion that the discovery is not patentable is rejected.

Interpreting the Patent

The Applicant for cancellation claims that the specification ONLY teaches attacks that use the redundancy arising from the Error Detection Code ERR, whereas claims 1 and 4 cover attacks NOT using this redundancy, and even attack methodologies  that have not yet been developed.

ITS-KIND-OF-FUNTO-DO-THE-IMPOSSIBLEThe Patentee claims that attacks that only use ciphertext with the GSM Standard, and do not use the Error Detection Code ERR are not possible. The Patentee claims that since the notice in the GSM Standard undergoes error correction before encryption, the notice and all the other redundancies that are included, all undergo error correction. Since the Error Detection Code in the GSM Standard is not systematic, i.e. it changes the original bits, a situation is created in which one cannot differentiate between redundancies arising from the Error Detection Code and other redundancies. Consequently, the patent claims attacks that use the redundancies from the Error Detection Code only or together with other redundancies.

Section 13(a) of the Law states:

The specification will end with the claim or claims that define the invention, so long as all the claims is fairly based on the Specification.

Regulation 20(a)(3) of the Patent Regulations detail the requirements of Section 13 and state that the claims should be brief and clear (succinct).

The claims define the scope of protection claimed in the Application. Interpretating (construing) the claims should be done in light of the patent document as a whole, including the specification and figures. However, one cannot incorporate into the claims something that is not stated in them. See Appeal 407/89 Zuk Ohr Ltd vs. Car Security Ltd et all. p.d. 48(5) 661 on page 691:

The opening position for fashioning an appropriate approach is that the patent documentation is a monolithic document that the inventor himself writes in his own words, and can draft as he pleases…the lack of clarity that exists regarding the correct interpretation of this or that phrase in the claims can be solved by reference to the rest of the patent document, but one cannot cherry pick phrases from the specification that support the Patentee’s suggested interpretation, whilst ignoring other terms that are included there.

To correctly construe the claims one has to consider the explanation of various terms that the parties disagree about.

Cryptanalysis

bruteThe main dispute between the parties is whether independent claims 1 and 4 include Brute Force Attacks and whether the term cryptanalysis includes attacks of this nature. Professor Herzberg, the witness for the Applicants for Cancellation, considers that the term cryptanalysis includes Brute Force and supports this contention with various related publications. The patentee argues that persons of the art reading the patent will note that brute force is not related to and so will not consider this as being included.  The patentee also claims that there is no obligation to actively disclaim things not claimed and he wasn’t obliged to note that brute force is not covered.

There doesn’t seem to be any disagreement that the cryptanalysis field does include brute force attacks. However, as the patentee argues, construing terms used in claims is not done in a vacuum. The Deputy Commissioner cites re Zuk Ohr to state that claim interpretation is to be based on the specification, but also Opposition 179995 Camtek vs. Orbotech to support the view that ambiguity works against the patentee. The Deputy Commissioner concludes that persons of the art would not consider that the claims intended to include brute force attacks since they are not mentioned at all. She thinks that the Applicant for Cancellation is reading brute force into the claims to try to discredit them as reading on the prior art, whilst Professor Herzberg himself acknowledges that ciphertext attacks are excluded, so disallows this interpretation as being detached from the text.

Professor Herzberg acknowledges that neither the patent nor the corresponding scientific paper relate to brute force attacks. Furthermore, GSM communications are not susceptible to brute force attacks since the key is 64 bit. Professor Herzberg acknowledges that based on the Lenstra publication, brute force would require hundreds of thousands of years, whereas after 5 hours of preparation, the suggested attack takes a PC one second.

Access

accessThe parties also disagree regarding the meaning of the term access which appears in the specification as follows:

“Known plaintext means that the attacker has access to encrypted messages as well as to the messages that were encrypted.

Ciphertext only means that the attacker has access only to the encrypted messages, and has no access to the messages before they were encrypted.”

The Applicant for Cancellation considers that the term is not defined in the specification at all, and the correct explanation includes not just certain knowledge regarding the pre encrypted message, as claimed in the patent, but also the possibility of knowing something to a significant level of certainty. However, it transpires that Professor Herzberg’s opinion in this matter is not based on the literature. Under cross-examination, Professor Herzberg conceded that the term ‘access’ is a professional term that has a meaning in encryption, contrary to that claimed in his second Opinion.

Furthermore, Professor Herzberg opined that the papers by Golic, Biryukov and Lucky Green  required certain knowledge of the communication prior to encryption, but not actual physical access and the ability to manipulate the notice. Thus the dispute is whether or not ‘access’ includes the possibility to know something to a high degree of certainty.

Hellman and Diffie consider that a  ciphertext only attack is one wherein the attacker only has general knowledge of the system that he is attacking, or of the message prior to encryption. This general knowledge includes statistical data or suspicions regarding the elements, see Diffie II page 399:

“Usually the worst circumstance from the point of view of the cryptanalyst is to have nothing available to him but the material he has intercepted, knowledge of the general system, and some general knowledge of his opponent’s messages. This may be limited to a knowledge of the statistical properties of the language in use (e.g., in English, the letter E occurs 13 percent of the time) and a knowledge of certain probable words (e.g., a letter probably ends “Sincerely yours,”). Although occasionally a cryptanalyst may be ignorant even of the language or system in use, this is the weakest threat to which a system is normally subjected, and any system which succumbs to it must be considered completely insecure. It is called a ciphertext only attack.”

Here the Deputy Commissioner tried to pin Professor Herzberg down regarding whether the example is known plain-text or ciphertext only. That as may be, Professor Herzberg failed to provide evidence for his explanation of the meaning of the term ‘access’. Consequently, the Deputy Commissioner rejects the explanation that the term access means ‘the possibility of knowing something to a high likelihood’ and accepts the patentee’s definition that the term ‘access’ implies certain knowledge regarding the content of the notice.

The Corresponding American Patents

US flagThe Applicant for Cancellation claims that unlike the Israel patent, the issued US patents related to use of the Error Detection Code ERR and were thus narrower. They also note that the European and US examiners considered that Brute Force Attacks were part of the Prior Art, and brought the Opinion of Patent Attorney Colb to support this contention.

The Deputy Commissioner noted that 3825/85 Yeshayahu Balas vs Naan Metal Factory p.m. 5743(1) 177, 188 rules that foreign patent office conclusions do not obligate the interpretation of Israel patents. However statements made by the Patentee in foreign jurisdictions can estoppel him locally. (see 513/89  Interlego A/S vs Exin-Lines S.A. p/d/ 48(4) 133.).

In this instance, there is no judicial ruling or admittance by the patentee but merely an Examiner’s determination in ‘192 that without the claims otherwise specifying the method of cracking the code, brute force is included.

The Applicant for cancellation considers that the Examiner’s position changed the claim wording, however the Opinion of his witness Colb does not support this conclusion. In fact, on cross-examination, Colb admitted that he hadn’t examined the prosecution file-wrapper at all!

Claim 6 of the corresponding ‘477 patent recites:

“A method for processing an encrypted GSM digital communication comprising:
intercepting a wireless signal containing an encrypted first ciphertext;
recovering a cryptographic key used to encrypt the first ciphertext by a ciphertext only cryptanalysis of the first ciphertext through the use of processing circuitry,
wherein said cryptanalysis comprises deriving equations for bits of key-stream used to encrypt at least a portion of the first ciphertext,
wherein said deriving includes either:
(1) XORing together bits of the first ciphertext based on an error correction coding scheme, or
(2) XORing bits of said first ciphertext with bits which are an output of an error correction coding scheme; or (3)
both; and
using the recovered cryptographic key to decrypt or produce a second ciphertext wherein said first and second ciphertexts are encrypted using the same cryptographic key.”

Under cross-examination, Dr Barkan stated that implementation of the patent had to use the Error Detection Code ERR with or without redundancies in the source code.

After considering Colb’s interpretation of the claims without reference to the specification or prior art, and with reference to Dr Barkan’s testimony, the Deputy Commissioner ruled that the scope of the claims was limited to attacks of the “ciphertext only” using the Error Detection Code, and did not include Brute Force Attacks.

Novelty and Inventive Step

Novelty

noveltyThe Applicant for Cancellation considers that the claims cover all methods of cryptanalysis using cipher-text only on A5/1 and A5/2 and therefore include methods beyond those described, including Brute Force which is known, and consequently the claims lack novelty. Furthermore, even if the claimed invention is novel, it is not inventive as there is no proven commercial success, which the secondary tests for identifying inventiveness require, and the community of cryptanalysts did not relate to the patent in any significant manner.

The patentee claims that Applicant for Cancellation submitted a bunch of publications that relate to theoretical attack of the A5 algorithm using known plaintext, and these are not actually practical and simply assess the attackability of the A5 algorithm without actually attacking it. The patentee alleges that his invention is an important breakthrough of cryptanalysis of cellular networks that received acclaim in the academic and the business worlds. It causes those responsible for securing GSM in Europe and the US to stop using one of the algorithms that was cracked. He further alleged that his discovery was the first that allowed the code to be cracked and that the prior art does not describe how the Error Detection Code can be used to break the encryption. Furthermore, even if the ambit of the claims is construed as including Brute Force attack, the Applicant for Cancellation has failed to provide any document that explains how Brute Force can be used to attack a ciphertext only communication that uses the GSM Standard.

The Deputy Commissioner then cited Section 4 of the Israel Patent Law 1967:

An invention is deemed new if it was not published, in Israel or abroad, before the application date –
(1) by written, visual, audible or any other description, in a manner that enables a skilled person to make it according to the particulars of the description;
(2) by exploitation or exhibition, in a manner that enables a skilled person to make it according to the particulars thus made known.

To cancel the novelty of an invention, the prior art publication should describe the elements of the invention in a way that enables average persons of the art to implement the invention as claimed (See Appeal 345/87 Hughes Aircraft vs. State of Israel, p.d. (4) 45:

The first rule is that to prove novelty destroying prior publication one has to identify a single document that describes the invention in its entirely and it is not sufficient to create a mosaic of different documents to create a general picture.

Hughes also states that:

A general description is insufficient to remove novelty if it is not enabling and does not provide enough signposts leading to the invention of the patent.

The requirement to teach the whole invention is also explained in Appeal 4867/92 Sanitovsky vs. Tams ltd et al, p.d. 50(2), 509:

On one hand, the defense of a patent includes not just that described in the claims, but also the core of the invention [MF – what the British case-law refers to as the pith and marrow in a somewhat odd mixed metaphor] (section 49). On the other hand one can claim a lack of novelty when accused of infringement (section 4) not just when a piece of prior art describes all the elements of the invention, but also then the prior discloses the core of the invention.

The essence of the invention is that part that is central and essential to the workings of the invention in contradistinction to elements that can be substituted for or left out entirely. The main core will remain protected even if an essential element is switched for another that performs the identical function. 
Page 515-516. [MF-this seems to be the so-called doctrine of equivalents].

See also Appeal 793/86 Michael Porat. vs. Z.M.L. Modern Medical Equipment, p.d. 44(4); 578 pages 583-584.

The Deputy Commissioner does not consider it reasonable to construe the claims to include Brute Force attacks on a ciphertext only communication using the GSM Standard. In this regard she notes that professor Herzberg himself admitted that if brute force was actively disclaimed or the claims related specifically to using the Error Detection Code, none of his referenced prior art would not anticipate the invention.

The main pieces of prior art were then considered and dismissed as not reading on the invention.

DIFFIE I – the Patentee argued that this relates to the DES encryption which is a block cipher, whereas the A5 encryption is a stream cipher. Consequently, the Error Detection Code redundancies of the GSM Standard cannot exist in DES. That as may be, the Diffie I citation is from 1977 and predates the GSM standard. Professor Herzberg admitted that it does not relate to cellular networks. The Deputy Commissioner ruled that it is not novelty destroying with regards to the claimed invention.

PESONEN – this relates to Brute Force Attacks. Section 4.1 states:

A real-time brute-force attack against the GSM security system is not feasible, as stated above. The time complexity of the attack is 2^54 (2^64 if the ten bits were not zeroed out). This requires too much time in order to be feasible in eavesdropping on GSM calls in real-time.

… The attack can be optimized by giving up on a specific key after the first invalid keystream bit. This would cut the required time down by one-third. The attack can also be distributed between multiple chips, thus drastically decreasing the time required [12].”

The patentee noted that even if this was technologically feasible, the attacker would have to know which key was the right one and this would require knowledge of the redundancies which is not described in Pesonen. Under cross-examination Professor Herzberg was forced to concur that this was the case. The attack described is a known plaintext attack and not a ciphertext only attack. Although Pesonen related to redundancies, Professor Herzberg admitted that this was an inaccurate choice of words.

The Deputy Commissioner ruled that neither Diffie nor Personen anticipated that attack described and claimed by the patentee.

LENSTRA describes a brute force attack on a 64 bit encryption key. However, in 1992 a Pentium II 450 MHz (then state of the art) would have taken 226000 years to break a 64 bit key. That as may be, the present invention does not use brute force, and Lenstra’s approach would still take hundreds of thousands of years.

LUCKY GREEN – This is an attack on the GSM Standard that was described by Borisov in 1999 and states:

“Need 2 frame (114 bits each) of ciphertext whose plaintext has a known difference.
 – Easy to find, since many frames are silence.”

Further

“After A5/2 was reverse engineered, it was immediately cryptanalyzed by Goldberg, Wagner and Green. Their attack is a known plaintext attack…
Apparently, this attack is not applicable (or fails) in about half of the cases…”

Thus Lucky Green is a plaintext and not a ciphertext only attack and is therefore not novelty destroying.

In this regard, David Wagner, one of the authors of Lucky Green, corrected someone who thought that the patented approach was anticipated by Lucky Green:

“John Doe Number Two wrote:
>It’s nice to see someone ‘discovering’ what Lucky Green already figured-out years ago. I wonder if they’ll cut him a check.

 [– David Wagner]  No, no, no! This is new work, novel and different from what was previously known. In my opinion, it is an outstanding piece of research.

Barkan, Biham and Keller establish two major results:

  1. A5/2 can be cracked in real-time using a passive ciphertext only attack, due to the use of error-correcting coding before encryption.
  2. All other GSM calls (including those encoded using A5/1 and A5/3) can be cracked using an active attack. This attack exploits a protocol flaw: the session key derivation process does not depend on which encryption algorithm was selected, hence one can mount an attack on A5/2, learn the A5/2 key, and this will be the same key used for A5/1 or A5/3 calls.”

The Deputy Commissioner was convinced that the Lucky Green Attack is theoretical and assumes some knowledge of the content. As Biryukov put it:

“The attacker is assumed to know some pseudo random bits generated by A5/1 in some of the frames. This is the standard assumption in the cryptanalysis of stream ciphers, and we do not consider in this paper the crucial issue of how we can obtain these bits in fielded GSM systems.”

Lucky Green was only a theoretical known plaintext attack, but in 2006, the patentees showed how it could be converted into a ciphertext only attack in E. Barkan, E. Biham and N. Keller, Instant Ciphertext-only Cryptanalysis of GSM Encrypted Communication, Technion – Computer Science Department – Technical Report CS-2006-07 (2006). [MF – Note this post-dates the filing date of the present invention].

The sides concur that Lucky Green only works half the time on known plaintext. Barkan reasons that it works when the 11th bit is an 0 and not a 1.

The Deputy Commissioner concluded that none of the citations read on the invention, and noted that the Opposer did not present any argument as to how they could be coupled together to render the invention obvious.

Secondary Considerations of Inventability

The Deputy Commissioner referenced various pieces of evidence that showed that the invention answered a long-felt need, was widely adopted and received peer acclaim. This was done in response to the Applicants for Cancellation arguing that the secondary tests mentioned by Hughes were not fulfilled.

Dependent Claims

The Deputy Commissioner then related to the dependent claims and showed that these were novel and inventive.

Ruling by Ms Jacqueline Bracha Concerning Cancellation of IL 155671 to Barkan et al., 23 August 2017

COMMENTS

To my mind, despite the Applicant for Cancellation bringing up the secondary tests indicative of inventive step, it was totally unnecessary of the Deputy Commissioner to relate to these. They can be used to support an argument that something borderline is inventive, but the converse is not true. The lack of one or all of them cannot be used to argue that a patented invention is not inventive. Similarly , having established that the independent claims are novel and inventive, there was no need to relate to the dependent claims. In the past, I’ve criticized decisions which knock out the independent claims and assume that the dependent claims fall with them. That is not the case. The dependent claims may be used to establish a narrower patent. However, where the independent claims survive attack, there is no need to consider the dependent claims.

Reading between the lines, it seems to me that the Applicant for Cancellation never had a problem with the patentability of the disclosed method, but considered that the claims were too broad and included other known techniques such as Brute Force. It might have been cheaper and more convenient for all concerned, for the parties to have negotiated a narrowing of the claims to specifically refer to using the Error Detection Code ERR instead of a long, protracted and expensive cancellation proceeding.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: