METHOD AND SYSTEM FOR STRONG AUTHENTICATION AND SECURE COMMUNICATION

(TUPLEZZ: combines the words TUPLE and PUZZLE.)

TUPLEZZ is the Enigma Machine of the 21st century without Enigma's 

major flaw (i.e., a letter could never be encoded as itself)

 

-- Patented: US 11,290,444 B2 -- Google Patents

and up for licensing, sale or startup --

. White Paper .

Cybercrime is one of the biggest challenges that humanity is facing and cybersecurity innovation is paramount to our economy and national security so I thought of a method – which I called TUPLEZZ – that has the following strengths:

.1. . .TUPLEZZ is a Challenge-Response authentication method that makes it impossible for an attacker to replicate even when the hacker has the static ID and Pw of the User and he (the attacker) has recorded (screen capture and keylogging) all previous login sessions of the User.

.2. . . This method doesn’t require a third party or time synchronization.

.3. . .Due to the infinite number of possible formulas that can be used, a brute force attack to figure out the algorithm is impossible.

.4. . .The Client can log in even in the absence of the token with no need to contact the Server (or a third party) and no need for a cell phone.

.5.. .The AOTC (Authenticated One Time Challenge) makes phishing impossible. AOTC replaces the OTP (One Time Password) used by other methods.

.6. . .The use of a login counter means that TUPLEZZ is automatically updated after each login session. Therefore this method doesn’t need to be updated but if the Server’s policy requires periodic updates they can be done.

.7. . .The encryption it provides is unbreakable because TUPLEZZ can provide a key length as large as the message and only used once (because each new message will be associated with a new AOTC which will result in a new unique key), which is what Claude Shannon showed to achieve the so called perfect secrecy.

.8.. .This method requires that both parties (Server and Client) contribute with a random input every time the user logs in, which results in a unique authentication method which is superior to anything else tried so far.

TUPLEZZ in plain English

(Or read the non-provisional at USPTO or Google Patents)

BRIEF DESCRIPTION OF THE DRAWINGS 

The embodiments are illustrated by way of example, and not by way of limitation in the figures of the accompanying drawings in which like reference numerals are used to refer to similar elements. 

FIG.1 is a flow chart illustrating the server’s method to identify the client. 

FIG.2 is a flow chart illustrating the client’s method of identifying the server and complete the second step of the login process when using a token. 

DETAILED DESCRIPTION OF THE INVENTION 

Some implementations of the present invention are discussed below. While specific implementations are discussed, it should be understood that this is done for illustration purposes only. A person skilled in the relevant art will recognize that other components and configurations may be used without parting from the spirit and scope of the invention. 

In the following description, for purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding of the embodiments. It will be apparent, however, to one skilled in the art that the embodiments can be practiced without these specific details. 

Specific details used: 

- list_a, list_b, list_c and the Challenge have 72 distinct characters. Also list_c_a = list(zip(list_c, list_a)) and list_c_b = list(zip(list_c, list_b)); 

- The Challenge is a 72 characters long list: len(Challenge) = 72; 

- the Challenge has 4 (four) Active Elements (ActiveElement_i, i = 0, 1, 2 and 3) in predetermined positions inside the list; 

- The Client’s token can provide 8 different but valid Responses to each Challenge in any login session. One of the 8 valid Responses can also be calculated by the User in the absence of the token; 

- The Response to the challenge is 8 (eight) characters long: len(Response_i) = 8; 

- The Server’s Authentication for the challenge is 6 (six) characters long: len(Server_Auth) = 6; 

- For more clarity some Python syntax is used. 

Part 1: Strong authentication 

1a. With token: For convenience we’ll consider that the Response (the answer to the challenge) can use 72 distinct characters. Some businesses only accept 62 distinct characters for a password/Response (no special characters) while others accept more than 10 special characters for a total of more than 72 distinct characters: this method works for any number of valid characters. 

We need to define a few lists before describing this authentication method, so: 

For 72 valid characters the basic list of characters, list_c (list of characters), is: 

For readability the list_c and Sample Challenge are presented table-like (a 12X6 table). 

The Challenge will be random.shuffle(list_c) and one random example is shown below:

The Challenge is displayed table-like so a token that allows for data input by means of an optical interface -- Optical Character Recognition (OCR) in this case -- can easily capture the whole information in one take. 

No two Challenges can be identical, as shown in Fig. 1. All Challenges contain a number of ‘Active Elements’ (ActiveElement_i) which can always be found on the same predetermined secret positions and will be used in computing the Response (one of the valid 8 possible Responses the token can provide or the User’s Response in the absence of the token) to the Challenge. 

Each character in list_c has a corresponding number from 1 to 72. The corresponding number for each character is determined as follows: list_a = list(range(1,73)) which then is shuffled (random.shuffle(list_a)):

so the correspondence character-number is clearly shown in list_c_a = list(zip(list_c, list_a)):

While in most cases the Challenge and list_c_a used in the algorithm described below will provide the level of security needed by the two parties, this method will present an added level of security which may be used whenever required. This extra level of security is provided by list_b. 

In this example list_b is determined as follow: list_b = list(range(-99, 99), then it is shuffled

(random.shuffle(list_b)) and then to make sure that len(list_b) = 72: list_b = list_b[:71]:

The range(-99, 99) has been chosen for purposes of explanation. Any range larger than 72 will be just fine. 

So now list_c_b = list(zip(list_c, list_b)):

Note that list_c_a and list_c_b can be combined in list_c_a_b = list(zip(list_c, list_a, list_b)) but because the method presented herein is designed to also allow the User to compute his Response when the token is not available we shall use, for purposes of explanation, the lists list_c_a and list_c_b. 

Both Server and Client’s token will have the same software with list_c_a and list_c_b saved (they can be saved as tuples) so they can both authenticate each other. Also the Client should have the list_c_a saved in a safe place (a hardcopy will do) in case the token becomes unavailable. The lists list_c_a and list_c_b will be kept unchanged indefinitely or for as long as the Server’s policy allows it. 

The authentication method presented herein works as follows: 

Let’s consider that the predetermined positions for the 4 Active Elements (ActiveElement_i) in list Challenge are: Challenge[17], Challenge[29], Challenge[51] and Challenge[66] so in the Sample Challenge above the Active Elements will be: 

ActiveElement_0 = ‘$’ 

ActiveElement_1 = ’J’ 

ActiveElement_2 = ’9’ 

ActiveElement_3 = ‘i’ 

The corresponding numerical values of the characters ‘$’, ‘J’, ’9’ and ‘i’ in the list_c_b above  are: 

b(‘$’) = 58 

b(‘J’) = 45 

b(’9’) = -4 

b(‘i’) = 43 

where b(ActiveElement_i) is the numerical correspondent of the character ActiveElement_i in list_c_b.

When creating the software for a certain Client the Server will generate a random.shuffle(list_c) and divide it in 8 equally long (for simplicity, in this example, all sublists will be 9 characters long) sublists: listP_1, listP_2, ..., listP_8 so no two lists can have any element/s in common since all 72 characters have been used: 8*9 = 72. Both parties’ software will keep the 8 lists listP_i and their corresponding sets of formulas indefinitely unless the Server decides otherwise. 

A set of 7 distinct formulas is associated to each listP_i. The formulas will use as arguments the b(ActiveElement_i) or a(ActiveElement_i) when there is no list_c_b.(Note that there can be more or less than 4 Active Elements). 

Here is an example of the lists listP_i for some random.shuffle(list_c):

When the Client receives the Challenge from the server the token will read the Challenge and will generate a random character (Rc) out of the 72 characters in the list Challenge or list_c and then will identify the listP_i which contains that character. Let’s say the random character Rc is ‘f’ which belongs to listP_6 above and let’s say that the following 7 formulas are associated to listP_6:

F1(P_6) = 4*b(ActiveElement_2) - 13 

F2(P_6) = (3*b(ActiveElement_1) - 2*b(ActiveElement_0))/4 

F3(P_6) = (b(ActiveElement_3))**2 - 22 

F4(P_6) = (b(ActiveElement_2 -5))**3 + 16 

F5(P_6) = 5*F1(P_6) - 34 

F6(P_6) = 7*F2(P_6) +19 

F7(P_6) = 6*(F4(P_6) - F2(P_6)) - 29

Sample Formulas associated to listP_6 

Note that there is an infinite number of possible formulas and they can be as complicated as desired. Relatively simple formulas are used in this presentation. 

Now using the values 58, 45, -4 and 43 determined above we shall have:

F1(P_6) = 4*(-4) - 13 = -29 

F2(P_6) = (3*45 - 2*58)/4 = 4.75 

F3(P_6) = 43**2 - 22 = 1827 

F4(P_6) = (-4 - 5)**3 + 16 = -713 

F5(P_6) = 5*(-29) -34 = -179 

F6(P_6) = 7*4.75 + 19 = 52.25 

F7(P_6) = 6*(-713 - 4.75) - 29 = -4335.5 

The results of the formulas can be negative and decimal numbers, so to make them positive integers in range(1,73) the next step is to do:

a(Fj(P_k)) = abs(int(Fj(P_k))%72 +1 

where j and k are natural numbers: 1<= j <=7 and 1<= k <= 8 and a(Fj(P_k)) stands for the numerical values for which the corresponding characters will be identified in list_c_a: 

a(F1(P_6)) = abs(int(-29))%72 + 1 = 30 

a(F2(P_6)) = abs(int(4.75))%72 + 1 = 5 

a(F3(P_6)) = abs(int(1827))%72 + 1 = 28 

a(F4(P_6)) = abs(int(-713))%72 +1 = 66 

a(F5(P_6)) = abs(int(-179))%72 +1 = 36 

a(F6(P_6)) = abs(int(52.25))%72 + 1 = 53 

a(F7(P_6)) = abs(int(-4335.5))%72 + 1 = 16 

In list_c_a to the 7 numbers that have been calculated will correspond the following characters, which being part of the Answer/Response to the Challenge we shall call A1 to A7: 

30 -- ‘%’ = A1 

5  --  ‘*’  = A2 

28 -- ‘y’ = A3 

66 -- ‘D’ = A4 

36 -- ‘a’ = A5 

53 -- ‘g’ = A6 

16 -- ’4’ = A7

While the Random Character Rc can be on any of the 8 positions in the Response, let’s assume that, according to the algorithm agreed upon by the two parties in this particular case, Rc is on the 3rd position from the left so the Answer/Response is of the form:

 A1A2RcA3A4A5A6A7 

Thus for the Sample Challenge, Sample list_c_b, Sample list_c_a and the 7 formulas associated to listP_6 above the Client’s token will come up with the Response: 

%*fyDag4 

When receiving the Response from the Client the Server will pick up the character in the 3rd position -- Rc which is ‘f’ in this case -- and use the same formulas (because f is an element of listP_6 to which a unique set of 7 formulas is associated) and the same Challenge and list_c_b and list_c_a to compute the Response and then compare it with the Client’s Response.

Now that we know how the Client’s authentication is computed using the Challenge’s Active Elements, list_c_b, list _c_a and the sets of 7 formulas it’s time to mention that the Server will also authenticate itself when displaying the Challenge. The Server’s authentication can be 6 characters long so it can be the 13th column in the table-like displayed Challenge so it would be quite convenient for the OCR to read both the Challenge and the Server’s authentication in one take. While the Server can have multiple valid authentications, like the Client, in most cases one authentication (using the same Active Elements like the Client or different ones on predetermined positions and one set of formulas known by both parties) should be enough.

The lists list_c_a, list_c_b, positions of the Active Elements, the lists listP_i and the sets of formulas will be kept unchanged indefinitely by both parties or until the Server decides to update one or more of them.

The static formulas presented can be made dynamic by adding a login counter* starting with a seed value and incremented with a certain rate at each login: the value of the login counter will be added to each formula so at each login all formulas will be different from all the previous login sessions. Login counters are way more reliable and easier to install and maintain than OTPs’ time synchronization. A login counter will not be used in the User’s List formulas for obvious reasons we shall see below.

* The Server’s authentication (the 6-characters-long 13th column in our example) for each login session could be the value of the login counter encoded using the Active elements for that specific login session so the two parties will make sure that their login counters are in sync. 

Fig. 1: 

When the Server receives a login request 102 it will ask for the static username and password of the Client 104 (Client and User are used here interchangeably).

If the Client enters the correct values in the first step -- 106 and 108-YES -- of this 2FA then the Server randomly generates a Challenge 110 and compares it with the previous Challenges that have been used and saved in the Server’s Challenges Database 114. 

If/when the Challenge is new 112-YES the Server will authenticate it 116, add it to the Database 114 and display 118 for the User the Authenticated One Time Challenge (AOTC) for him/her to solve it . 

The User enters the Response 120 and if the Response is correct 122-YES the access is granted 126. If the User enters the wrong Response then 124 the Server will take the appropriate action.

 Fig. 2: 

When the Server displays the Challenge the token optically reads 210 the Challenge. 

The token compares the Challenge with the previous Challenges that have been used and saved in the Client’s Challenges Database 214. 

If the Challenge is not an AOTC the token will take the appropriate action 216. 

If the Challenge is new and correctly authenticated by the Server 212-YES the Client’s Challenges Database 214 is updated with this new Challenge. 

The token randomly generates Rc 218. 

The token computes the Response 220 using the set of formulas associated to Rc. 

User enters Response 120.

The Challenge is a list containing only the characters that can be used in a password/Response for that specific server.

1b. Without token: 

In situations where it is acceptable for the Client to skip checking if the Challenge is an AOTC (Authenticated One Time Challenge), the Response can be computed without a token. Even if an attacker tricked the Client into providing a Response that Response can’t be used again anyway. 

When the token is unavailable (damaged, misplaced, dead battery, stolen and so on) the Client can still provide the Response by using only list_c_a and a set of formulas as simple as ax + b. 

The User will save list_c_a, one particular listP_i which we call the User’s List (listP_8 in this example) with its specific 9 characters and the set of formulas associated with the User’s List in a safe place that can be as simple as a hardcopy.

When Rc is one of the 9 characters in listP_8 (User’s List) above that will notify the Server that the list_c_b (and the login counter, if any) is/(are) ignored. There is no way to know for an attacker (assuming that the attacker somehow knows the User’s List, which is highly improbable) or even the Server whether the Client can’t use the token (and thus computes manually) or the token just happened to randomly generate a character from the User’s List. Out of the 8 lists (listP_i) only one (in this example we chose listP_8 to be the User’s List) is ignoring list_c_b (and the login counter, if any) to make it easier and faster for the User to compute the Response. When computing the Response by himself the Client has to place any of the 9 characters of the User’s List on the predetermined position for Rc (the 3 rd position from the left in this presentation).

The User will ignore list_c_b and only use list_c_a for computations by replacing b(ActiveElement_i) with a(ActiveElement_i) in the first step of computations presented in Sample Formulas associated to listP_6 (of course that in this case the formulas associated with listP_8 will be used). Then he will complete the rest of the steps of the algorithm. 

If the Client always (that is with or without token) manually enters the Response using the keyboard instead of providing the Response by other means when the token is available then even an attacker who managed to install a RAT (Remote Access Trojan / Remote Administration Tool) capable of performing keylogging and screen capture on the user’s computer will not be able to figure out whether the Client used a token or not to answer the Challenge. 

The user’s set of formulas are so simple that he can easily do the computations himself (all PCs and smart phones have a calculator with all the needed operations including the MOD function). There is an infinite number of simple formulas of the form ax +b and no attacker can be successful trying to brute force attack the infinite.

[00xyz] In many situations it should be sufficient for a Client with no token to compute less than 7 characters (Ai’s) for the Response. For instance the Client can compute only 4 or 3 Ai’s, place them and the Rc on the predetermined places in the Response and fill the other positions with random characters -- it will be up to the Server to set up the details for this very convenient authentication method. 

Of course that the Server can provide the Client with banks’ style Transaction Authentication Numbers (typically, there are 50 TANs printed on a list) or backup codes (Google provides a list of 10) for situations when the token is unavailable, but while the TANs and the backup codes have to be re-delivered again and again each time they expire, the ability of a TUPLEZZ User to compute a valid Response by himself is unlimited.

Part2: Secure communication and transaction signing. 

The party who initiates the secure communication randomly generates a Challenge, encodes the plaintext with the key_final explained below and submits to the other party the Challenge and the ciphertext. For simplicity we consider that Response_k is provided by the set of formulas as- 11 sociated to listP_k (1 <= k <= 8).

All Responses concatenated (‘Response_1’ + ‘Response_2’ + ... + ‘Response_n’) create key_0. If the plaintext is longer than key_0 (len(plaintext) > len(key_0)) the next key (key_1) can be created from the original Responses each one multiplied by 2 and then concatenated and then the two keys are concatenated. If the plaintext is still longer than key_0 + key_1 the multiplying method is repeated (this time by 3) and so on until len(plaintext) <= len(key_0 + key_1 + ..) = len(key_final). Note: The series that will provide the numbers used to multiply the responses doesn’t have to be the set of natural numbers (1, 2, 3, 4, ..., n) but it can be any series (and there are an infinite number of them) the two parties agree upon. Because no two keys are identical (key_0 =/ key_1 =/key_2 and so on) statistical analysis (for instance the one proposed by Charles Babbage) to break the code is ineffective. A key length** as large as the message and only used once is what Claude Shannon showed to achieve the so called perfect secrecy

** Of course that the key can be of any length from a minimum acceptable length to len(key_final) = len(plaintext). 

Because in this method the Challenge accepts multiple valid Responses there are an infinite number of ways to use these Responses to create a key_final of a desired length.

For transaction signing: The server sends an AOTC and a request for a signature. Any valid Response from the client can be used as a signature. If the signature is required to be longer than one Response then the algorithm will concatenate n valid responses to that specific AOTC such as len(Response_1 + .. + Response_n) >= len(signature) and the server will consider the first m characters as a valid signature, where m = len(signature). Or the client algorithm can do the job and return to the server the appropriate substring as the m-long signature. Of course that a more convenient understanding between the two parties (server-client) would be for the len(signature) to be a multiple of len(Response).

Some final notes: 

- The method presented herein is designed to allow the User to provide a valid Response to the Challenge with or without a token. While for purposes of explanation we described a version with 8 possible Responses (7 ‘with token’ and 1 ‘with or without token’) the number of possible Responses can be anywhere from as little as 2 (1 ‘with token’ and 1 ‘with or without token’) to as many as 72 (71 ‘with token’ and 1 ‘with or without token’).

- The Server will provide the Client with the token or the software for the token in a safe manner.

- The token has a camera and a screen capable of displaying the required number of characters a Response has. If the token also contains a flash memory it will make it quite convenient for the tens of millions of people who already carry a flash memory with them -- so the token will not come as an inconvenience at all. If the token’s camera has 2 modes: OCR and a James Bond-style spy camera the device will appeal to even more people. Ideally a Client can use a token for multiple Servers which use this 2FA method. Depending on its complexity the token can have a different number of buttons. 

- In any login session only 2 elements will be randomly generated: the Challenge by the Server and the Rc (Random character) by the token to identify which set of formulas to use. In the ‘no token’ situation the User will randomly pick up a character from the User’s List (listP_8 in this presentation).

- It is up to the Server to update the list_c_a and/or list_c_b and/or listP_i and/or the formulas and/or the position of Rc if and when that is considered necessary. 

- While an OCR was used in this presentation, any other safe manner of reading the Challenge can be used. 

- The len(Challenge) can be (1) smaller than len(list_c) in which case not all elements of list_c will show up but the Response can have any elements from list_c whether they are in the Challenge or not; or(2) larger than len(list_c) in which case some elements will be repeated. 

- In many situations list _c_a will offer the desired level of security so list_c_b can be ignored and the computations will be done by the token using only list_c_a like the Client does when the token is not available.

- There are many people who love numbers (how popular Sudoku is worldwide doesn’t come close to saying the whole story) who might enjoy using for authentication a light version (only list_c_a, only one set of formulas and no Rc) of this method without any token and, eventually, having to compute only 3 or 4 Ai’s as explained in [00xyz] except that in this ‘no token’ situation there is no need for an Rc. 

- Tokens/key fobs which utilize this method can also be used for authentication to objects such as doors or automobiles.

DRAWINGS

CONTACT  -  HOME