Secure communications without key exchange
Contents
Supervisors
Honours students
Project guidelines
Project description
All existing cryptographic schemes involve, one way or another, the sharing or exchange of a cryptographic key. An open question is: can secure transmission be achieved without any form of key exchange? No one has ever achieved this, so this is an exciting project.
An analogy is to suppose Bob wishes to transmit a written message to Alice; Bob hides the message in a box that he securely padlocks before sending it to Alice. After receiving the box, Alice adds a second padlock and sends the box back to Bob. Then Bob unlocks his padlock, leaving the box still secured by Alice's lock, and sends it back to Alice who can then remove her lock, open the box and read the message.
Notice that neither Alice nor Bob shared their keys. They both kept them secret. This is the aim. This is called the KS-cipher or Kish-Sethuraman cipher. But nobody has ever figured out a way to do this mathematically. Once a mathematical description can be made, we can then translate that into real electrical signals.
Notice in the mechanical example, the position of the two padlocks commutes. Mathematically, we know that a simple 2D rotations and XOR operations also commute and so could be candidates. However, you can trivially show that an eavesdropper can crack these schemes, and so they do not work.
So what we want you to do is to extend the idea of data being encoded in a 3D space (instead of 2D) and then be rotated randomly to hide the data. Does that work? Then try 4D and so on. It's possible 6D might work but we are not sure yet.
As part of the project we'd like you create animations to help understand rotations in higher dimensions, such as shown here: http://eusebeia.dyndns.org/4d/vis/10-rot-1
An extension of this project that you should work with in parallel is to use internet round-trip times as a source of randomness for an alternative implementation. Bob and Alice repeatedly send packets back and forth. There will be random timing variations. But there will be a degree of correlation between Alice and Bob, that is not shared by Eve. The idea is to investigate an error correction protocol that can improve the fidelity of the key received by Bob, but where any scheme adopted by Eve simply increases her error. Bob and Alice have the advantage of multiple resends until the key is finally distilled. Although this process is slow, we are not concerned by speed for key distribution. The important thing is to establish proof-of-concept at any speed. We shall call this the RTKS-cipher, or the random time Kish-Sethuraman cipher.
Approach and methodology
The easiest way to describe rotations in higher dimensions is to use Geometric Algebra, which is a very powerful tool that engineers and computer scientist are starting to get excited about. This form of mathematics is surprisingly easy and all the operations are just like multiplying out brackets. We will show you how this works and you can pick this up very quickly.
We would also like you to use Matlab to simulate the encoding of messages and to perform possible operations on them that an eavesdropper could use. This way you can prove which schemes can be cracked. We would also like you to have a go at analytical proofs.
For the RTKS-cipher case, perform experiments by communicating between two different internet nodes and record the resulting bit stream. Then record the bit streams that Eve receives depending on the location of her node. Probably just try to two worst-case nodes, which would be (i) in the same room as Bob, and (ii) in the same room as Alice. You can then compute the cross-correlation between Bob's bit stream and Eve's bit stream, to demonstrate if Eve has been able to distill any information or not.
Expectations
- We don't really expect you, in this project, to solve the entire problem of perform secure communication without key exchange.
- What we are more interested in is you exploring the problem and doing some tests. We'd like you to create some animations to help visualize the properties of rotations in higher dimensions. We'd like you to record and compare bit streams received by Bob and Eve in the RTKS case.
- If by chance you totally crack the problem, it will be equivalent to solving a famous problem in computer science called the "N vs. NP" problem, which will make you famous overnight. Also there is a $1,000,000 prize for anyone who can do that.
- But if you don't get there for the million bucks, don't worry, we want you to just have fun understanding the problem and work by looking at ways of eliminating some of the easier cases. This will then give you enormous appreciation for cryptography and the underlying techniques. And you will have learned a lot of useful methods.
- To get good marks we expect you to show a logical approach. Do simulations as well have having a go at analytical proofs.
- We expect all the written work to be place on this wiki. No paper reports are to be handed up. Just hand up a CD with your complete project directory at the end. The entire project directories of each group member can go in separate folders on the same CD or memory stick. You won't be getting the CD or stick back.
- It is expected that you fill out a short progress report on the the wiki each week, every Friday evening, to briefly state what you did that week and what the goals are for the following week.
- It is important to regularly see your main supervisors. Don't let more than 2 week go by without them seeing your face briefly.
- You should be making at least one formal progress meeting with supervisors per month. It does not strictly have to be exactly a month, but roughly each month you should be in a position to show some progress and have some problems and difficulties to discuss.
- The onus is on you to drive the meetings, make the appointments and set them up.
- You are expected to make a YouTube presentation of your whole project. You should alo consider making 3-4 short instructional YouTube videos to walk a future user through any software and tools you develop.
Relationship to possible career path
This project will familiarize you with techniques in encryption, decryption and data security. It will also improve your software skills. You will learn about geometric algebra, which is a powerful tool for engineers. The types of jobs out there where these skills are useful are in computer security, comms, or in digital forensics. The types of industries that will need you are: the software industry, e-finance industry, IT industry, telecoms industry, ASIO, defence industry, etc.
See also
- CSI Adelaide: Was Trayvon Martin murdered? 2013
- CSI Adelaide: Was Trayvon Martin murdered? 2013 weekly progress
References and useful resources
If you find any useful external links, list them here:
- An initial exploration of the KS-cipher using geometric algebra
- The original KS paper
- Klappenecker's remarks on the KS-cipher
