End to end encryption

• US 10,225,265 B1
• Filed: 04/15/2016
• Issued: 03/05/2019
• Est. Priority Date: 04/15/2016
• Status: Active Grant

• Current Assignee: Snap, Inc.
• Original Assignee: Snap, Inc.
• Inventors: Sankuratripati, Subhash
• Primary Examiner(s): Pwu, Jeffrey C
• Assistant Examiner(s): Ambaye, Samuel
• Application Number:
  US15/099,719
• Time in Patent Office: 1,054 Days
• Field of Search: 382154, 713171
• CPC Class Codes: H04L 63/0442 wherein the sending and receiving network entities apply asymmetric encryption, i.e. different keys for encryption and decryption cryptographic mechanisms or cryptographic arrangements for public-key encryption H04L9/30
• CPC Class Codes: H04L 63/061 for key exchange, e.g. in peer-to-peer networks cryptographic mechanisms or cryptographic arrangements for key agreement H04L9/0838
• CPC Class Codes: H04L 63/123 received data contents, e.g. message integrity
• CPC Class Codes: H04L 9/0838 Key agreement, i.e. key establishment technique in which a shared key is derived by parties as a function of information contributed by, or associated with, each of these network architectures or network communication protocols for key exchange in a packet data network H04L63/061
• CPC Class Codes: H04L 9/0891 Revocation or update of secret information, e.g. encryption key update or rekeying
• CPC Class Codes: H04W 12/033 of the user plane, e.g. user's traffic

Abstract

Systems and methods for end to end encryption are provided. In example embodiments, a computer accesses an image including a geometric shape. The computer determines that the accessed image includes a candidate shape inside the geometric shape. The computer determines, using the candidate shape, an orientation of the geometric shape. The computer determines a public key of a communication partner device by decoding, based on the determined orientation, data encoded within the geometric shape. The computer receives a message. The computer verifies, based on the public key of the communication partner device, whether the message is from the communication partner device. The computer provides an output including the message and an indication of the communication partner device if the message is verified to be from the communication partner device. The computer provides an output indicating an error if the message is not verified to be from the communication partner device.

Claims

1. A method comprising:

accessing, at a computing device, an image, the image including a geometric shape;

determining that the accessed image includes a candidate shape inside the geometric shape;

determining, using the candidate shape, an orientation of the geometric shape;

determining a public signing key (B) of a communication partner device by decoding, based on the determined orientation, data encoded within the geometric shape;

receiving a message at the computing device;

verifying, based on the public signing key of the communication partner device, whether the message is from the communication partner device;

providing an output including the message and an indication of the communication partner device if the message is verified to be from the communication partner device;

providing an output indicating an error if the message is not verified to be from the communication partner device;

comparing the public signing key determined by decoding the data encoded within the geometric shape to a preexisting public key for the communication partner device;

marking the preexisting public key as trusted in response to the comparison determining the public signing key and the preexisting public key are equivalent; and

communicating with the communication partner device using the preexisting public key based on the preexisting public key being marked as trusted.

2. The method of claim 1, further comprising:

generating, at the computing device, a private key (a) of the computing device;

computing a public signing key (A) of the computing device, the public signing key of the computing device being computed according to an equation;

A=g^a mod p, wherein p is a prime number that exceeds a threshold, and g is a primitive root modulo p;

computing a shared secret (s) of the computing device and the communication partner device according to an equation;

s=B^a mod p;

decrypting the received message using the shared secret; and

encrypting, for transmission to the communication partner device, a second message using the shared secret.

3. The method of claim 2, wherein p, g, A, and B are publicly accessible values, and wherein the private key (a) of the computing device is a secret value stored securely at the computing device.

4. The method of claim 2, further comprising:

periodically modifying a value of the private key (a) of the computing device after a passage of a predetermined time period or after sending a predetermined number of messages;

re-computing the public signing key (A) of the computing device based on the modified value of the private key (a) of the computing device;

notifying the communication partner device of the re-computed value of the public signing key (A) of the computing device; and

re-computing the shared secret (s) of the computing device and the communication partner device based on the modified value of the private key (a) of the computing device.

5. The method of claim 2, further comprising:

receiving a notification that the public signing key (B) of the communication partner device has changed; and

re-computing the shared secret (s) of the computing device and the communication partner device based on the changed value of the public signing key (B) of the communication partner device.

6. The method of claim 1, wherein accessing the image comprises:

accessing the image via a camera of the computing device.

7. The method of claim 1, wherein accessing the image comprises:

receiving the image via a web browser, a social networking application, or a messaging service.

8. The method of claim 1, wherein determining that the accessed image includes the candidate shape inside the geometric shape comprises:

detecting a shape within the geometric shape;

comparing the detected shape with a set of reference shapes to determine a similarity score; and

determining that the similarity score exceeds a threshold.

9. The method of claim 1, wherein the geometric shape comprises a rectangle with rounded corners, and wherein determining the orientation of the geometric shape comprises:

determining an upward direction of the candidate shape; and

setting an upward direction of the geometric shape based on the upward direction of the candidate shape and based on a direction of at least one side of the rectangle.

10. The method of claim 9, wherein the set upward direction of the geometric shape is perpendicular or parallel to the at least one side of the rectangle.

11. The method of claim 9, wherein a ray corresponding to the set upward direction of the geometric shape and a ray corresponding to the determined upward direction of the candidate shape make an angle of less than 45 degrees.

21. The method of claim 1, further comprising:

receiving the preexisting public key for the communication partner device from a server; and

computing a public signing key of the computing device, and storing the public signing key on the server.

22. The method of claim 21, further comprising receiving an updated key of the communication partner device from the server, and receiving an instruction from the server to reencode a message for the communication partner device.

23. The method of claim 1, further comprising:

generating, at the computing device, a private key (a) of the computing device;

computing a shared secret (s) of the computing device and the communication partner device according to an equation;

s=B^a mod p, wherein p is a prime number that exceeds a threshold; and

decrypting the received message using the shared secret.

24. The method of claim 23, further comprising:

encrypting, for transmission to the communication partner device, a second message using the shared secret.

12. A non-transitory machine-readable medium comprising instructions which, when executed by one or more processors of a computing device, cause the computing device to perform operations comprising:

accessing an image, the image including a geometric shape;

determining that the accessed image includes a candidate shape inside the geometric shape;

determining, using the candidate shape, an orientation of the geometric shape;

determining a public signing key (B) of a communication partner device by decoding, based on the determined orientation, data encoded within the geometric shape;

receiving a message;

verifying, based on the public signing key of the communication partner device, whether the message is from the communication partner device;

providing an output including the message and an indication of the communication partner device if the message is verified to be from the communication partner device;

providing an output indicating an error if the message is not verified to be from the communication partner device;

comparing the public signing key determined by decoding the data encoded within the geometric shape to a preexisting public key for the communication partner device;

marking the preexisting public key as trusted in response to the comparison determining the public signing key and the preexisting public key are equivalent; and

communicating with the communication partner device using the preexisting public key based on the preexisting public key being marked as trusted.

13. The non-transitory machine-readable medium of claim 12, the operations further comprising:

generating, at the computing device, a private key (a) of the computing device;

computing a public signing key (A) of the computing device, the public signing key of the computing device being computed according to an equation;

A=g^a mod p, wherein p is a prime number that exceeds a threshold, and g is a primitive root modulo p;

computing a shared secret (s) of the computing device and the communication partner device according to an equation;

s=B^a mod p;

decrypting the received message using the shared secret; and

encrypting, for transmission to the communication partner device, a second message using the shared secret.

14. The non-transitory machine-readable medium of claim 13, wherein p, g, A, and B are publicly accessible values, and wherein the private key (a) of the computing device is a secret value stored securely at the computing device.

15. The non-transitory machine-readable medium of claim 13, the operations further comprising:

periodically modifying a value of the private key (a) of the computing device after a passage of a predetermined time period or after sending a predetermined number of messages;

re-computing the public signing key (A) of the computing device based on the modified value of the private key (a) of the computing device;

notifying the communication partner device of the re-computed value of the public signing key (A) of the computing device; and

re-computing the shared secret (s) of the computing device and the communication partner device based on the modified value of the private key (a) of the computing device.

16. The non-transitory machine-readable medium of claim 12, the operations further comprising:

receiving a notification that the public signing key (B) of the communication partner device has changed; and

re-computing the shared secret (s) of the computing device and the communication partner device based on the changed value of the public signing key (B) of the communication partner device.

17. The non-transitory machine-readable medium of claim 12, wherein accessing the image comprises:

accessing the image via a camera of the computing device.

18. The non-transitory machine-readable medium of claim 12, wherein accessing the image comprises:

receiving the image via a web browser, a social networking application, or a messaging service.

19. The non-transitory machine-readable medium of claim 12, wherein determining that the accessed image includes the candidate shape inside the geometric shape comprises:

detecting a shape within the geometric shape;

comparing the detected shape with a set of reference shapes to determine a similarity score; and

determining that the similarity score exceeds a threshold.

25. The non-transitory machine-readable medium of claim 12, the operations further comprising:

generating, at the computing device, a private key (a) of the computing device;

computing a shared secret (s) of the computing device and the communication partner device according to an equation;

s=B^a mod p, wherein p is a prime number that exceeds a threshold; and

decrypting the received message using the shared secret.

20. A system comprising:

one or more hardware processors; and

a memory comprising instructions which, when executed by the one or more processors, cause the one or more processors to perform operations comprising;

accessing an image, the image including a geometric shape;

determining that the accessed image includes a candidate shape inside the geometric shape;

determining, using the candidate shape, an orientation of the geometric shape;

determining a public signing key (B) of a communication partner device by decoding, based on the determined orientation, data encoded within the geometric shape;

receiving a message;

verifying, based on the public signing key of the communication partner device, whether the message is from the communication partner device;

providing an output including the message and an indication of the communication partner device if the message is verified to be from the communication partner device;

providing an output indicating an error if the message is not verified to be from the communication partner device;

comparing the public signing key determined by decoding the data encoded within the geometric shape to a preexisting public key for the communication partner device;

marking the preexisting public key as trusted in response to the comparison determining the public signing key and the preexisting public key are equivalent; and

communicating with the communication partner device using the preexisting public key based on the preexisting public key being marked as trusted.

26. The system of claim 20, the operations further comprising:

generating, at the computing device, a private key (a) of the computing device;

computing a shared secret (s) of the computing device and the communication partner device according to an equation;

s=B^a mod p, wherein p is a prime number that exceeds a threshold; and

decrypting the received message using the shared secret.