Code Breakers

‘They served in silence’

Prologue

“6 January, 1995. Manila, Philippine, local police were called on for an apartment fire.

Ramzi Ahamed Yousef

At their arrival they have found few interesting objects. A Toshiba laptop, random batch of chemicals and some materials used in bomb making. An open file on the laptop revealed a plan forsimultaneously bomb twelve US airliners over the pacific.The police found several files from the laptop which were all encrypted. When they decrypt the files using special software, they have found out that the files contained important messages linking many terrorists, bomb making techniques and plans of mass destructions. All these evidence pointed towards a very important person. He was the world’s most wanted terrorist at the time. “Ramzi Ahamed Yousef”, one of the masterminds of the 1993World Trade Centre bombing. The plot was stopped and he was arrested at a Pakistani guest house by Pakistani Inter-Services Intelligence Directorate and Special Agents of the U.S. Diplomatic Security Service. He was sentenced to life in prison without parole. It was a major victory for international law enforcements and once again it revealed the importance of cryptography in the world of war.

World War II (1939-1945) was the golden era of cryptography. It was a very busy time for cryptologists all around the world. Under the command of specialised branches of U.S Army and Navy, the top notch cryptologists played a significant role in paving the paths for the front line all over the world by intercepting secret Nazi German and Japanese codes and breaking them, especially by eavesdropping enemy’s diplomatic communications.
In 1917 the army created a cipher bureau within the Military Intelligence Division. Combined with the Radio Intelligence Unit they carried out all the intelligence communication services in Europe during the World War I. The Army Signal Corp was introduced and they assumed the responsibilities in decoding enemy communications. These services provided by the intelligence services at that time initiated the idea of forming one unified body of intelligence in code making and code breaking. This later led to the initiation of the NSA (National Security Agency, USA).
A key point in making allied counter strategies during the World War II was breaking the Nazi Germany secret code generated by their own cipher machine called The Enigma.

The Enigma Machine

German soldiers using an Enigma machine during the second world war

The Enigma machine is an advanced cipher machine developed by the Germans at the end of the World War I. It was used by the German military as their main device to secure wireless communications until the end of World War II. Main reason for the success of the enigma machine was that it used a set of rotors and a wired system which enabled to encrypt their secret messages uniquely and presumably in an unbreakable manner. The possible encryptions per letter on the machine were 2280. It’s simple operational functionality and the durability was another reason for this machine to be trusted among the Germans.
To send an encrypted message, the operator had to set the Enigma’s plug wirings and the rotor wheels to a predefined initial combination known to him and to the receiving operator. These combinations were kept in a registry and changed daily for extra security. Then the sending operator typed in the plain text message letter by letter to the enigma machine while it goes through the wiring and lights up a different letter on the upper panel of the enigma. The operator wrote down each of those lit up letters.

After typing in the whole message sender had the encrypted message which is a sequence of strings which means nothing. Then the encrypted message got transmitted through a standard Morse code radio transmission. Then the receiving operator wrote the received encrypted message, set his Enigma machine to the same pre-defined combination of rotor setting and then typed the message in to the machine. Then the Enigma lit up its original letter for each replacement letter.

The Bomb

The answer to the enigma machine by the allied forces was the ‘Bomb’. Conceptualised by the Poles, Designed by the British and built by the Americans, it was capable of figuring out all possible rotor combinations and to decrypt enemy’s Enigma codes one by one. Deciphered information given by the Bomb gave accurate detailed locations of German submarines in the Atlantics to the Allied Naval units.

Bletchley Park was the government’s intelligence communication headquarters at the time which facilitated about 10,000 code breakers. Situated 40 miles to the north of London, it was the central intelligence station that continuously had been eavesdropping Germany all through World War II until the D Day. The employees here were hired in an unorthodox manner where they were chosen from regular people, cross word fanatics, chess champions to 200 crypto analysts and mathematicians from various universities. Two of the outstanding characters among the Bletchley staff were Alan Turing and Gordon Welchman, Alan Turing, who is the father of the computer, developed the idea of the Bomb.

Bletchley Park, also known as Station X

In his replication the Bomb’s rotors were wired in a similar way as the Enigma. All its rotors were connected and driven by a motor. Each rotor had 104 contacts (26*4) which were connected together. The Bomb was used in testing if the crib fits to the given message. The machine simply tried all 26*26*26 possible cases. If a possible key was found, the bomb stopped. The correctness of the key was tested on a normal Enigma manually. At least 200 of these machines were built and located all over Great Britain. Later high speed bombs for the naval Enigmas were built in USA. However, the existence of the Bomb was kept as a secret from the Germans. Although In 1996, the Americans published secret work by Turing on the Bomb, some details have remained unknown until today.

Alan Turing

JN-25

During the war against the Japanese, the allied code breakers came across another complex numeric code called the JN-25. It was the most secure encryption cipher used in communication by the Imperial Japanese Navy (IJN). Unlike the Enigma, JN-25 could not be broken by machines and it was broken by shear efforts of cryptologists with their pencils and paper. Cryptologists had to find patterns by analysing all the intercepted messages in order to break JN-25. Armed with an important decoded JN-25 intercepted message, Admiral Chester Nimitz (Commander in Chief, United States Pacific Fleet) had a huge advantage against the Japanese fleets during the war. In May 1942, intercepts coded with JN-25 revealed a plan of a trap made by the Japanese on the US aircraft carriers near the island of Midway. By knowing the trap in advanced Nimitz made a trap of its own and surprised the Japanese strike force. For the Japanese this was the first defeat after 300 years.

A JN-25 Message

Along with the smart devises such as The Bomb and top brains fuelling the cryptographic race there were still many short coming. The effectiveness of the intelligence services was undermined by the lack of uniformed rational unit. One example of this was the Pearl Harbour Attack by the Japanese on December 7, 1941. Several hours before the bombs fell on the Pearl Harbour, an U.S code breaker found out that a surprise attack by the Japs were imminent. Since there was no efficient methods of relaying this message it was too late when the message arrived one hour after the attack. The overall death toll reached 2,350, including 68 civilians, and 1,178 injured. This event literally changed the world.

After the final victory had been achieved in 1945, the American government and policy makers identified the importance and value of having one unified agency for intelligence communication. After seven years the president Harry Truman, distressed at the obvious weaknesses in the intelligence structure, ordered an analysis in 1951 and acted on the investigation in the following year. A new agency, the NSA (National Security Agency, USA) was created by a top secret executive directive on October 24, 1952. By freeing from its subordinations, it was to be directly accountable to the secretary of defence. A 1984 presidential directive assigned the NSA responsibility for computer security, and, in a 1988 directive, responsibility for its own operations security training. Through this career-oriented service, the agency conducts its own recruiting and employment programs to ensure a skilled and sophisticated work force. NSA even manufactures their own hardware such as special microchips which they integrate to their enciphering machine. They keep all their actions as top secret in order to keep the internal government communication safe from foreign code breakers. NSAs success is triumphed not only by their high tech machine power but also with their brain power as well. They were tested to their limits time after time during its service.

One time pad

One time pad encryption is a multi layered process that uses random numbers to encrypt plain text into ciphered code. The simplicity and the robustness of this technique is remarkable and still believed to be unbreakable with today’s supercomputers if used correctly. However human error coursed by a soviet code clerk helped the allied cryptologists to break the code. There are multiple methods to apply the one time pad and below is one of such applications used by the Soviets during the beginning of the cold war. Assumed that the plain text to be encrypted is “Retreat at dawn”. First step of the encryption is the “Code Book”. A Code Book has words, listed alphabetically along with corresponding numbers that represent each word. According to the Soviets code book the words were replaced by a four digit number. Both the sender and the recipient were given two copies of the Code Book. One copy is used by the sender and another copy which is formatted differently is used by the receiver. After the Code Book conversion the plain text would be replaced by a number of four digit values.

E.g.: Retreat at dawn >> 0441 0412 2123 9000

9000 represents the end of the sentence. Then rearrange the 4-digit numbers into 5-digit numbers by moving the left-most digit from the number group to the right, over to the adjacent number group on the left. Since there is a shift of some digits one digit to the left, you will find that you run out of digits for the last numbers, so simply add zeros until the last number has 5 digits

E.g.: 04410 41221 23900 00000

Next step is done using another code book called the One Time Pad Book. It is a book which has rows of randomly generated five digit numbers. There will be only two copies of the same One Time Pad and one will be given to the sender and the other to the receiver. These random five digit numbers will be added to the earlier (04410 41221 23900 00000) message using a special arithmetic addition (Chinese). Any digit carried over is not used in the addition. This adds to the complexity of this encryption.

04410 41221 23900 00000 (The plain text message replaced with 5-digit numbers from Code Book)).

+

23402 89524 94742 00425 (random numbers copied from the One-Time Pad book).

______________________
27812 20745 17642 00425 (the encrypted message.)

The message is now ready to be transmitted. The person at the receiving end of the transmission must decrypt the message in reverse order. In order to do this, both he and the sender must have duplicate one-time pad books. The recipient also destroys the one-time pad page(s) that he had used to decode the message.
As the NSA continued their investigations lead by the information reviled through broken Soviet Multi layered messages, it was told that close to 60 people were brought to justice under the ”Venona” project.
The NSA continued their course throughout the Cold War by contributing immensely to the game of inelegance. They have been upgrading their own league of intelligence communication as the 21st century brought the world itself to an information age. NSA now deals with a new breed of challenges. Many research and experiments have been undertaken at NSA’s secret laboratories in developing new innovative methods and technologies to face the new era of cyber warfare.

Data Encryption Slandered (DES)

NSA has been involved in public policy making, both directly and indirectly to other departments. NSA was a major player in the debates of the 1990s regarding the export of cryptography. Another involvement of NSA is the development of the “DataEncryption Slandered” also known as the DES developed by the IBM. DES was selected as the official Federal Information Processing Standard (FIPS) by the National Bureau of Standards in 1976. DES is a block cipher based on a symmetric key algorithm that uses a 56 bit key to each 64-bit block of data.

NSA worked closely with IBM to strengthen the algorithm against all except brute force attacks and to strengthen substitution tables, called S-boxes. Conversely, NSA tried to convince IBM to reduce the length of the key from 64 to 48 bits. Ultimately they compromised on a 56-bit key. There were various criticisms from various parties stating that the NSA made two changes to DES. It tweaked the algorithm, and it cut the key size by more than half making it less secure. After two decades later, academics discovered that the tweaks made by the NSA made the DES more secure. This meant that the NSA was two decades ahead with their state of the art technology among the rest.

During the middle of 1990s, DES was broken by using a brute force attack. After that a newer version of the DES with the same mathematics but a longer key, called triple-DES was introduced.

In July 1990 the NSA showed their interest in a new encryption method called RSA. Much earlier during early 1980s NSA has opposed the adoption of the RSA technology by the Department of Commerce. NSA opposed RSA’s system precisely because it was so effective; its codes were virtually untraceable. Agency feared the chance of this technology getting into enemies hands which may put the national security into a vulnerable position. NSA and FBI claimed RSA’s encryption techniques made it possible for spies and criminals to plan and act without fear of detection by intelligence or law enforcement agencies.

RSA

Its name comes from combining the first letters of names of the inventors (Rivest, Shamir and Adleman) of this system. RSA Data Security developed and marketed the technology which enables its users to communicate and transfer data in a highly secure manner. The technology was using a public key encryption methodology which stood far ahead from previous encryption technologies. RSA is being implemented largely in e commerce protocols and many more sectors where maximum data security is essential.
RSA Cryptosystem involves a Public key and a private key where the public key can be known by everyone but the private key can be only known by the decoder of the message. Public key will be used for the encryption of the message and the private key will be used for the decryption.
First step of the RSA system is the “Key Generation” for the algorithm. It is being done as below.

• Randomly chose two distinct prime numbers (q, p) of similar bit length.
• Computer the “modulus” (n) where n = pq.
• Compute φ(pq) = (p − 1)(q − 1).
• Choose an integer (e)
  • 1 < e < φ(pq),
  • e and φ(pq) share no divisors other than 1 (i.e., e and φ(pq) are co prime).
  • e will be the public key exponent.
• Determine d using modular arithmetic where

• d will be the private key exponent

Next is the encryption;

• Let the message be M the receiver will transmit his/her public key (n, e).
• Receiver will keep the private key a secret.
• Sender will then turn the message M in to integer m (0
• Computes the cipher text c where;
  • c = me mod n
• c get transmitted to the receiver.

Decryption;
The receiver will recover m from c

• m = cd mod n

Then, by using the padding schema again m can be transferred to be M (Original Plain Text Message)
In 1993 the NSA countered the issues they had with the RSA cryptosystem with the introduction of their own “Cipher Chip”. The Cipher chip was a form of a “Big Brother” which was embedded in to the cryptosystem as a backdoor in order for the NSA to eavesdrop on RSA communications. It was a third key, which gave NSA access to any encrypted information and this was secretly kept only with the NSA. RSA organized a conference to unify the US computer industry against the government’s effort to impose its system. At this conference held in January 1994 many leading hardware and telecommunication industry representatives defended their arguments against the government’s efforts on large scale violation of privacy. They jointly rejected the Cipher Chip.

Tuesday, March 28, 2006
U.S. Department of Defence Agency Selects RSA Security Encryption Software

RSA BSAFE® Crypto-C Micro Edition Meets National Security Agency’s Suite B Cryptography Requirements
Bedford, MA— RSA Security Inc. (Nasdaq: RSAS) today announced that the National Security Agency selected RSA® BSAFE® Crypto-C Micro Edition (ME) encryption software for use in a classified communications project.
http://www.rsa.com/press_release.aspx?id=6677

In 1998 RSA announced a contest with prize money of $10,000 to whoever was able to break a code encrypted in the DES (Data Encryption Standard) which was the government standard at the time.
This contest was won by a two man team, a computer privacy activist and a hacker who broke the code in 56 hours. This contest further proved the weaknesses of the outdated standards the government was using at the time.
The International Data Encryption Algorithm (IDEA) developed by X. Lai and J. Massey in 1991 was the encryption system which was introduced to replace the DES standard. It is also a symmetric block cipher, operating on 8 bytes at a time, just like DES, but with a key of 128 bits.
Almost all of the NSA’s work and involvement in development of encryption systems was unpublished and kept as secrets because of national security. Some of those work has been kept as classified to date.

Modern-day war on terrorism is keeping the NSA’s eyes and ears wide open for new threats and challenges in ways the world have never witnessed. NSA is carrying out modern day counter attacks to prevent such threats. It is debated to what extend the NSA’s arms and eyes reach. Some instances there has been reports of extreme actions taken by the intelligence agencies such as the NSA have seriously violated privacy of our own day to day life.

http://www.justice.gov/opa/documents/nsa_myth_v_reality.pdf

Above is a rationale by the U.S. Department of Justice to such allegations. It discusses the myths surrounding NSA’s eavesdropping programs and their legality.
Today NSA is responsible of more than 80% of both national and international intelligence activities with their roots reaching seven times further than CIA or any other service in America. It is been told that the NSA and CIA are monitoring all communications in America whether they are Internet, cellular telephone, regular telephone, books, newspapers, television, or any kind of communication broadcasts. The FBI has the Carnivore program to monitor and listen in on all Internet communications. These actions may prevent criminals and other terrorist sources attacking critical U.S. system and sabotaging day to day lives of American citizens. Such attacks may course destruction of a level same as 9/11 or a Pearl Harbor in today’s world. Such potential targets could be Share Markets, Public Transport Systems, Airports, banks and etc. If such an attack happens the country will fall in to anarchy while its transportation grid locks, its communications disrupted and its economy ruined. To prevent such electronic “Pearl Harbour attacks” NSA is developing defensive measures which are kept as well guarded secrets.
NSA is developing defensive measures which are kept as well guarded secrets and will continue to listen for trouble, like a doctor with a giant stethoscope pressed to the world.

References:

RSA (2010). – 6.2.2 What is the NSA? – Retrieved on 15th of May 2010 from

http://www.rsa.com/rsalabs/node.asp?id=2316

RSA Press Releases (Tuesday, March 28, 2006) on U.S. Department of Defense Agency Selects RSA Security Encryption Software – RSA BSAFE® Crypto-C Micro Edition Meets National Security Agency’s Suite B Cryptography Requirements – Retrieved on 20th of May 2010 from http://www.rsa.com/press_release.aspx?id=6677

Office of Public Affairs U.S. Department of Justice Washington, DC 20530 ( January 27, 2006) –

THE NSA PROGRAM TO DETECT AND PREVENT TERRORIST ATTACKS

MYTH V. REALITY – Retrieved on 05th of May 2010 from

http://www.justice.gov/opa/documents/nsa_myth_v_reality.pdf

Martin Oberzalek (April 4, 2000) – Breaking the Enigma – Retrieved on 10th of May 2010 from http://www.mlb.co.jp/linux/science/genigma/enigma-referat/node6.html

http://en.wikipedia.org

August 30, 2010 | Categories: Educational, Political | Tags: Alan Turing, Cold War, Enigma Machine, The Bomb, Warld War 2 | Leave a comment