Half a croissant, on a plate, with a sign in front of it saying '50c'
h a l f b a k e r y
Bite me.

idea: add, search, annotate, link, view, overview, recent, by name, random

meta: news, help, about, links, report a problem

account: browse anonymously, or get an account and write.

user:
pass:
register,


                 

Key Exchange using Torrent of Random Bytes

Randomly select bytes from a torrent of random bytes
  (+3)
(+3)
  [vote for,
against]

To use this method, an official torrent of random bytes is established for the public. It is called a "torrent" because it needs to be able to fill any normal computer as quickly as possible. This is to limit how much of the data any one person can store.

A user hoping to eventually create a key, saves randomly selected bytes from the stream along with their serial numbers. The serial numbers are merely the date, the time of day (to the second), and the sequence number for that second. For example:
"10:27:2016:10:52:12:1458791216" would be byte# 1,458,791,216 selected during the 12th second of 10:52 AM on October 27, 2016. The actual formatting used could be very different from that shown, of course.

For a key exchange to occur, two people --- let's call them Bob and Alice -- compare their serial numbers, over normal email, to see which bytes they have in common. If they discover that they have enough for the level of security they want, they agree to use some or all of those bytes.
The older a given byte, the greater its value for key material, since it's all the less likely anyone else would happen to have saved it.

For Eve to reliably replicate the keys Bob and Alice choose, she would need an enourmous, expensive system to ensure she could store enough of the byte stream to duplicate the overlap. That's in addition to being able to monitor their email communications.
Alvin, Sep 10 2016

NIST Randomness Beacon https://www.nist.go...t-randomness-beacon
Not a torrent, but similar. [notexactly, Sep 20 2016]


Please log in.
If you're not logged in, you can see what this page looks like, but you will not be able to add anything.



Annotation:







       I think I get this, even though I don't really understand much about cryptography.   

       Am I right in understanding that the torrent is basically a humongous one-time pad; would-be communicators grab random parts of the torrent, find which bits they have in common, and use them as their personal one-time pad?   

       If so, how secure would it be? If the torrent is very, very huge then it's unlikely that Bob and Alice will hold enough bytes in common to use as a one- time pad. If the torrent is less huge (making it more likely that they have downloaded bytes in common), then it becomes easier for Eve to just archive all the torrent and hence be able to eavesdrop on Bob and Alice. Or did I miss a step?   

       For most situations, shouldn't one assume that the eavesdropper may have resources several thousand times bigger than those of the communicators?   

       (Incidentally, I know Bob and Alice; they are two of the dullest people I have ever met and, unless you are really, really into 1950's pottery jugs, it's not worth eavesdropping on them.)
MaxwellBuchanan, Sep 10 2016
  

       It's not going to work, because what Max said.   

       Mallory (the NSA, MI5 or whoever) have the resources to store every byte generated, for any reasonable flow rate. It would be easier than what they're already doing.
Loris, Sep 10 2016
  

       Working out some numbers:   

       Say Mallory had 1000 hard drives of 10 terabytes each, that's 10^3 times 10^13 or 10^16 bytes total.   

       To make sure Mallory can only store half, we make the torrent 2*10^16 bytes.   

       Alice and Bob each store 10^9 bytes (a gigabyte) at random, they should have roughly 10^18 / (2*10^16) bytes or 50 bytes (400 bits) in common. That's about enough for a key, though maybe a little more could help, especially if Alice and Bob have fewer bytes in common with each other, and Mallory knows more of them, just by luck.   

       The torrent size in bits is 16*10^16. That would take 16*10^7 seconds over a gigabit ethernet link. That's around 5 years. Mallory might have some bigger hard drives by then.   

       If Mallory only had a tenth as much storage, or we can increase the torrent speed to 10 gigabits per second, that time comes down to 6 months.
caspian, Sep 11 2016
  

       Yes, this system definitely needs improvement.   

       I actually expected from the start, that this would be more of an interesting failure than a raging success. I only posted it to illustrate a concept. One of the worst aspects of it is the huge bandwidth it would consume in a world where there's no such thing as enough.   

       @MaxwellBuchanan
It sounds like you understand it as well as I do. There would certainly be security holes, due to big-budget computer systems.
Alvin, Sep 11 2016
  

       //Alice and Bob each store 10^9 bytes (a gigabyte) at random, they should have roughly 10^18 / (2*10^16) bytes or 50 bytes (400 bits) in common.//   

       They actually can't do that. At least, not without using significantly more than a GB. Each byte needs to be stored in some addressed manner. Here is a calculation for an arbitrary way of storing them:
  

       Each byte is addressed as the offset from the previous byte. Depending on how often we record bytes, we could run-length encode the offset. But I'm going to ignore that for simplicity and consider a 2-byte offset. The total cost is 3 gigabytes.
But how much of that 2*10^16 stream would that be able to handle? Well, let's suppose that we sample the feed... obviously the secure thing to do is sample at random, because otherwise we're easily compromised. But let's ignore that and calculate the maximum length range we could possibly get. So each offset is 0xffff (an offset of 65535+1), which because I'm feeling generous we round up to 10^5 - so the total range covered is 10^5 * 10^9 = 10^14, or one two-hundredth of the feed length. If you sample randomly within the range you can halve that figure. So we're talking at least a 3-byte offset, and a total cost of 4GB.
  

       We could store the bytes themselves in separate lists, but that won't help us because we while we save on storing the bytes themselves, we need to address the previous byte in its individual list.   

       And now consider actually trying to find bytes we share in common. Like playing snap with 10^16 pairs of cards.   

       Of course we could store values larger than bytes, and striated runs of values - or more complicated patterns. That reduces addressing cost. But probably the more you do that, the more you risk Mallory having a clever method of evesdropping.   

       *And* we're now all reduced to trusting this 'random' torrent, which is not a good thing.
Loris, Sep 14 2016
  

       This seems quit similar to a very old fashioned method.   

       "You remember the funny nickname we came up with for our waiter on the Alaska cruise we took last summer? Let's use his name as the password." Basically you refer to some bit of shared information that is unlikely to be known by someone else.   

       You're trying to make that systematic so it can be used more generally and more reliably. I agree with others that this particular implementation maybe flawed, but it's an interesting way to think about a potential password exchange method. [+] If you don't trust public/private encryption, believe that it will soon be broken, or have a secret that you would like to still be secret 20 years from now, some form of this could be good since it relies on memory not on computing power. Hmm... The problem is that if Eve has significant resources, how do you know she wasn't recording and archiving conversations on all the major cruise lines. She can find that nickname with just a little searching.
scad mientist, Sep 14 2016
  

       Nice Link [notexactly].   

       It's really sad that they felt the need to put the disclaimer:   

       "WARNING: DO NOT USE BEACON GENERATED VALUES AS SECRET CRYPTOGRAPHIC KEYS."
scad mientist, Sep 20 2016
  


 

back: main index

business  computer  culture  fashion  food  halfbakery  home  other  product  public  science  sport  vehicle