Post-Quantum Key Exchange in Telegram's MTProto Protocol

Abstract

Eksperter i feltet post-kvantekryptografi antar at kvantedatamaskiner vil knekke asymmetrisk kryptografi innen 30 år. Kvantedatamaskiner kan bruke allerede eksisterende algoritmer, som Shors algoritme, til å løse de matematiske problemene som moderne kryptografi er bygget på. Mer spesifikt er problemene heltallsfaktorisering og diskrete logaritmer vist usikre mot kvantedatamaskiner. Dette motiverer for integrasjon av nye kvantesikre kryptografiske løsninger i eksisterende protokoller for å sikre framtiden for kommunikasjon og informasjonsteknologi mot kvantetrusler. Det er startet opp flere standardiseringsprosesser for å utvikle nye post-kvantekryptografiske løsninger. En slik prosess ble startet opp av National Institute of Standardization and Technology (NIST) i 2017, hvor forskere og utviklere sendte inn sine kryptografiforslag med et mål om å avansere i konkurransen og til slutt å få sin løsning standardisert.

Denne masteroppgaven tar for seg usikkerheten rundt hva slags påvirkning integreringen av en av kandidatene fra NISTs standardiseringsprosess vil ha på en nettverksprotokoll. Påvirkningen på sikkerhet er teoretisk analysert gjennom å sammenlikne eksisterende sikkerhetsbevis og matematiske egenskaper. Ytelsespåvirkning er analysert og diskutert på bakgrunn av ytelsesmålinger. Denne masteroppgaven bruker SABER KEM som kandidat fra NIST-konkurransen, og meldingsapplikasjonen Telegrams protokoll, MTProro.

Masteroppgaven fremstiller et nytt design av MTProtos prosess for generering av autorisasjonsnøkkel ved å bytte ut kvantesårbare RSA og Diffie-Hellman med SABER KEM. Den konkluderer med at sikkerheten vil øke ved bruk av SABER. Resultatene peker på at også ytelsen vil bli bedre ved integrasjonen.

Surveyed experts in the field of post-quantum cryptography believe that quantum computers will break public-key cryptography within 30 years. Quantum computers can use already existing algorithms, such as Shor's algorithm, to solve the mathematical problems modern cryptography is built upon. Specifically, the problems of integer factorization and discrete logarithms are proven insecure against quantum computers. This motivates integration of new quantum secure cryptographic solutions to our existing protocols to secure the future of communication and information technology against quantum adversaries. There have been put in motion standardization processes to develop new post-quantum cryptographic solutions. One such process was initiated by National Institute of Standardization and Technology (NIST) in 2017, where researchers and developers submitted their cryptographic solutions with the goal of advancing in the competition and getting it standardized in the end.

This master's thesis addresses the uncertainty of how the integration of one of the candidates in the NIST standardization process will affect an existing network protocol. Effects on security are analyzed theoretically through comparing existing security proofs and mathematical properties. Effects on the performance are analyzed and discussed on the basis of existing performance measurements. The thesis uses the SABER KEM as chosen candidate from the NIST competition, and the messaging service application Telegram's protocol MTProto.

The thesis provides a new design of MTProto's authorization key generation process by replacing quantum vulnerable RSA and Diffie-Hellman with SABER KEM. It concludes that the security will be increased by integrating SABER. It is found that the performance will also theoretically be increased with the integration.