Massive MIMO Cryptosystem

New paper: “Physical-Layer Cryptography Through Massive MIMO.”

Abstract: We propose the new technique of physical-layer cryptography based on using a massive MIMO channel as a key between the sender and desired receiver, which need not be secret. The goal is for low-complexity encoding and decoding by the desired transmitter-receiver pair, whereas decoding by an eavesdropper is hard in terms of prohibitive complexity. The decoding complexity is analyzed by mapping the massive MIMO system to a lattice. We show that the eavesdropper’s decoder for the MIMO system with M-PAM modulation is equivalent to solving standard lattice problems that are conjectured to be of exponential complexity for both classical and quantum computers. Hence, under the widely-held conjecture that standard lattice problems are hard to solve in the worst-case, the proposed encryption scheme has a more robust notion of security than that of the most common encryption methods used today such as RSA and Diffie-Hellman. Additionally, we show that this scheme could be used to securely communicate without a pre-shared secret and little computational overhead. Thus, the massive MIMO system provides for low-complexity encryption commensurate with the most sophisticated forms of application-layer encryption by exploiting the physical layer properties of the radio channel.

MIMO stands for “multiple-input multiple-output.” I had to look that up.

In general, I’m not optimistic about the security of these sorts of systems. Whenever non-cryptographers come up with cryptographic algorithms based on some novel problem that’s hard in their area of research, invariably there are pretty easy cryptographic attacks.

So consider this a good research exercise for all budding cryptanalysts out there.

Tags: academic papers, algorithms, cryptanalysis, cryptography

Posted on October 15, 2013 at 6:27 AM • 32 Comments

Comments

Janne • October 15, 2013 6:39 AM

“Whenever non-cryptographers come up with cryptographic algorithms based on some novel problem that’s hard in their area of research, invariably there are pretty easy cryptographic attacks.”

So, if you have a really hard problem to solve in your field, reframe it as a cryptography method, then sit back and have a beer while the cryptographers solve it for you.

I wonder if there’s a business method patent in there somewhere?

Nick • October 15, 2013 7:14 AM

No patent – prior art. This is a variation of a tried and tested technique – speak your problem out loud and many helpful people will tell you the answer. Some might even be correct

Janne • October 15, 2013 7:28 AM

No patent – prior art. This is a variation of a tried and tested technique[…]

Ah, but nowadays we can add “… on the internet” at the end of the application. That seems to reliable make it an all new idea for the patent office.

Bear • October 15, 2013 7:47 AM

Prior literary art, even. If I understand this correctly, I used it in my 2002 novel Net Assets (http://www.bussjaeger.org/index.html#life-art3).

(Just for giggles, NA also included giving the feds an unreadable text printout of a crypto key (think Lavabit’s Levison) and mysteriously combustible fed compter centers (NSA’s Utah data center anyone?).)

Now if only someone would actually build the damned launcher.

bcs • October 15, 2013 8:40 AM

I think the paper falls to trivial black bag or rubber hose attacks.

Also, couldn’t Eve just duplicate whatever (presumably sub-exponential) setup steps Alice and Bob did? If there is some sort of trap door set up procedure (e.g. “by generating both the input and output setup simultaneously…”) then that should tell Eve a great deal about what the channel looks like. If on the other hand the key depends on a privileged physical position, then the system is hard to set up (non mobile) and likely very sensitive to multi-path, particularly changes in the multi-path environment, which turns into an effective DoS attack.

Stanislav Datskovskiy • October 15, 2013 8:50 AM

bcs,

the only crypto that doesn’t fall to the rubber hose method (“rectothermal cryptoanalysis”) is one where the user has no access to the keys. This is normally accomplished with a “panic zero” trigger. And even then one is faced with the problem of the inquisitor getting impatient, the soldering iron getting warmer and warmer, and you, the victim, haven’t any keys to cough up… This is why a cipher machine must not only include panic-zeroization, but it must do so in a public and obvious way.

Clive Robinson • October 15, 2013 9:05 AM

@ Bruce,

You are kind of missing the point with,

MIMO stands for “multiple-input multiple-output.” I had to look that up

In general the place you will find MIMO is in radio networks especialy cognative radio networks and it uses similar ideas to “spread spectrum” to increase the utilisation of a block of radio spectrum.

In Direct Sequence Spread Spectrum (DSSS) you spread the EM energy over a very wide bandwidth, several times that of the base channel coding rate and by doing this you get what is called “processing gain” which is in effect the ratio of the EM bandwidth to the base dandwidth. In theory this alows you to communicate in secret because the EM signal is well below the noise threashold and therefore in theory only recievable by the person(s) with the deconvolution code. However in practice EM radiation of any bandwidth followes the usual P^2 issue that to double the distance you have to radiate four times the power. So anybody within a range defind by the the square root of the processing gain to the transmit antena will see the signal above the noise threashold.

MIMO uses multiple antennas at both the transmitter and receiver which usually have considerable space diversity. The trick this time is to spread the power of the transmitter not across the frequency spectrum but across the physical space by sharing it amongst antennas. In theory you can operate such a system at or below the normal noise floor at the receiver as the signals from the various receiver antennas are cohearently added together. However you can also split the modulation across the carriers as well.

Thus the idea is you could in an appropriately clever system design both the transmitt and receive systems to work in a way such that you only receive all the baseband inteligence in places where the receiving antennas and orientations are correct.

Not knowing this in theory prevents evesdropping, in practice having appropriate receivers next to all the TX antennas will get you back all the baseband information… Which is a case the authors rule out in their argument.

However there are other arguments to consider on the security of such systems such as the size of the lattice (defined by number of TX and RX antennas) and the required physical space to put them in the word “massive” does have real physical meaning in this system –especialy where it’s desirable not to have antennas in eachothers “near field”– where as the number of bits in an RSA key does not. Also the size of antennas and frequency bands of interest puts such massive MIMO systems up into the range where manufacturing is going to prove “interesting” at best. And there are other asspects to consider and in all honesty this blog does not realy provide the space to look into them.

For those that want to know more you will probably first need to go and look MIMO up on Wiki there is a very basic introduction that provides links off to other articles. If you also go and look up Andrea Goldsmith’s other recent papers on cognative radio networks you will get further information.

However if you look back on this blog you will see the idea of security through space diversity EM systems has been discussed before in relation to securing NFC systems from evesdropping, and that certainly predates the date of this paper by quite some time, oh and does not suffer so easily from the “co-located Eve” issue.

Boyd • October 15, 2013 9:16 AM

As soon as anything different appears, machine gun it to pieces. Keep doing this for years until, one day, you find yourself cowering behind an air-gap hoping AES still works.

Clive Robinson • October 15, 2013 9:42 AM

Oh and whilst I remember MIMO only three degrees of “physical” freedom at any given antenns as explained by this paper (unfortunatly paywalled),

http://www.nature.com/nature/journal/v409/n6818/full/409316a0.html

Whilst this can be enhanced using othe “multiple access” techniques (time/frequency/code) there are real laws of physics imitations involved which means that “massive” realy does have physical significance.

I should also mention why the antennas need to be atleast twice the nearfield distance appart (ie a min of 4wavelength with non orthagonal dipoles, more with other antennas). It’s simply that beelow this distance what you are doing is in effect “beam forming” and this would reduce your security margin.

Markus Kuhn at Cambridge Labs has pointed out that the limitations given in the paper I’ve given might also explain why quantum computing is not taking off to well. But I’ll be the first to admit I’m not sufficiently knowledgable to reliably argue the case either way…

Matthias Urlichs • October 15, 2013 9:44 AM

@Boyd: Uh, what?
This is cryptography. Somebody is going to try and shoot holes through any system we can come up with.
The idea is to build something that doen’t have any holes, because if you’re not even trying, Eve is certain to find some.

Boyd • October 15, 2013 10:56 AM

@Matthias Urlichs: Uh, what?

Who is “we?”
Don’t tell me you “came up with” something…new? Oh no… you are in big trouble now! I don’t know what it is or how it works, but it is wrong and will never work. There! That’ll teach you.

zaker • October 15, 2013 11:20 AM

Did my masters in a subject close to this. It’s riddled with new notation math and weave heavily into machine learning theory. The basics of it is thinking of everything as a graph with several input and output nodes. And only by having knowledge off all(or sufficient) output nodes, you can know how the information traversed the graph. Anyone that doesn’t will have no possibility of receiving the message(information theoretically secure). Keywords will be ldpc, factorgraphs, network coding. And I believe that it might have some academic value, but it’s far away from practical use.

Jeremy • October 15, 2013 11:35 AM

If it is imperfect, but adds difficulty for interception, then it can still be useful as an additional layer.

Alfredo Ortega • October 15, 2013 12:02 PM

I believe this is a shared-secret schema, the secret being the combination of mimo-matrix and the location of both transmitters (that is, the channel between them).
I don’t see any difference with other similar schemas, the problem of key-distribution remains.

I think the strenght of this system is that even knowing all the parameters (position+MIMO matrix) if you cannot locate the eavesdropper receiver in the exact same location, it wont work.

However I don’t see it as practical as it only works in RF channels (no optical) and no-pure logic like other quantum-proof cryptosystem like McEliece.

H. Peter Anvin • October 15, 2013 12:07 PM

Red flag: “under the widely-held conjecture that standard lattice problems are hard to solve in the worst-case”. Typically for cryptographic purposes you care about the best case, or possibly the best case minus some set of avoidable trivial subcases.

Max • October 15, 2013 1:00 PM

In this work we offer a proof of security by showing that breaking our cryptosystem is at least as hard as solving well-known lattice problems in the worst case that are conjectured to require exponential running time.

That’s not a red flag. They claim that if you can break their cryptosystem, then you can solve lattice-problems in the worst case. And these problems are believed to be hard in the worst case. So there’s no problem as long as there is no error in their proof.

The following would have been a red flag: Arguing that if you can break the scheme, you can solve average-case lattice problems. And then saying: Since these problems are (believed to be) hard in the worst case, our system is secure. But that’s not at all what they did.

NobodySpecial • October 15, 2013 1:28 PM

@Janne – could be a great saving for computational chemistry groups.

Dear Abdul, we have encoded the message in the folding of this protein sequence… And then let the NSA do the hard work!

BJ • October 15, 2013 1:56 PM

@zaker

This sounds like TOR.

RSaunders • October 15, 2013 7:47 PM

While the n x m lattice problem might well exponentially hard, n and m are physical objects (antennas and collection or transmission amplifiers). In a crytographic community where we folks like 2^512 sized key spaces and change keys regularly, the 2^256 atoms in the observable universe are the only one’s we’re going to have for most things. Imagine the rekey time when changing the key implies building a new antenna farm for some interesting n.

Dirk Praet • October 15, 2013 7:56 PM

@ Stanislav Datskovskiy

the only crypto that doesn’t fall to the rubber hose method (“rectothermal cryptoanalysis”) is one where the user has no access to the keys…

Unless you’re using a shared-secret scheme, where for any decryption to happen you need M out of N keys. That way you can easily give up your key/passphrase/whatever and your files while still leaving your adversary with empty hands. I’ve mentioned the combination of Tomb and SSSS before on this blog. See also thegrugq’s presentation thereof at http://grugq.tumblr.com/post/58693149193/practical-data-security-for-travelers-to-via-the-uk .

@ Boyd

As soon as anything different appears, machine gun it to pieces.

Since when is discussion, analysis and other scrutiny of papers a crime or the equivalent of “machine gunning stuff to pieces” ? Are you familiar with any type of process for scientific or academic research or do you just take people’s word for every new idea you hear ?

Mike • October 15, 2013 10:27 PM

The following would have been a red flag: Arguing that if you can break the scheme, you can solve average-case lattice problems. And then saying: Since these problems are (believed to be) hard in the worst case, our system is secure. But that’s not at all what they did.

Admittedly, I haven’t read the paper, but although they may not have said it, it could be irrelevant anyway since the majority of cryptographically-interesting lattice problems share an average-case to worst-case equivalence. This is one of the prime motivations for looking into lattice problems for post-quantum crypto.

For those who may not understand the implications of this, consider the following:
Integer factorization (finding n factors, not finding all factors) is easy in the average case (ie. random integer), hard in the worst case (pq).
The majority of lattice problems are easy only in the best case, hard in the average/worst case.

ie. If you pick random input values for many lattice problems, it is provably equivalent within some small bound to picking the worst possible input values.

Wael • October 16, 2013 11:33 AM

Seems someone is using this blog to harvest ideas 😉
We discussed this here and here. And @RobertT also participated here… Maybe not exactly the same, but the idea seems close enough…
@Nick P, @Clive Robinson, @RobertT, we should ping these guys for academic integrity 🙂

Nick P • October 16, 2013 1:52 PM

@ Wael

Nice catch! It certainly happens. I sometimes see exact words or phrases used along with the idea. That’s rare, though. Clive usually mentions “been discussed here before by…” but leaves out references. Personally, I put stuff on here so that it will get stolen and benefit us as its embedded into things. Call it a “selfless act of security.” Would be nice if they gave more credit credit, though. 😉

Reminds me of a discussion I had with a potential business partner a year ago. I was pointing out how some of my ideas ended up in a major security product and that I had posted them here. The other person thought I meant I had written up source, corresponded with person in question, etc. I said, no it’s much simpler than that: I post lots of stuff on major blogs, they read it, and you can see strong similarities in their work afterward. Maybe it’s “independent invention,” maybe it’s influence.

All I know is they almost always try to make it like they were being totally original so as to get the fame and fortune. 😉

Brian M. • October 16, 2013 3:28 PM

@Clive Robinson:
+1!

The paper’s scheme is reliant on a massive MIMO channel, and if you don’t have that, it’s useless. I didn’t see any reference to an example of a physical set of commercial products. They mention using radio, but only gets a mention. If it’s not using spread spectrum, then it would be using, say, a large number of WiFi hotspots. I could see a combination of spread-spectrum and UDP being used for something like this, but I would never rely on it exclusively.

RobertT • October 16, 2013 6:23 PM

I’ll skip this discussion.
Lets just say that a little birdie whispered in my ear that certain ideas not currently in the public domain should remain that way.

BTW when they have something to say they dont actually whisper, and they communicate their displeasure in ways that are anything but subtle .

Wael • October 16, 2013 6:57 PM

@ RobertT

You have chosen…

Nick P • October 16, 2013 11:21 PM

@ Wael

“You have chosen”

Nice. Unlike “Indie,” he’s chosen to drink from the glass that comes with the gold and jewels. And unlike in the movie, it’s the wise choice for him. 😉

Wael • October 17, 2013 1:11 AM

@ Nick P

Under the circumstances, his choices were to drink from the glass with gold and jewels, or drink from his nostrils through a sack covering his head while lying down on a tilted board. “They” are not easily amused 😉
I wouldn’t have chosen “poorly”, if it were me.

notaghostatall • October 17, 2013 2:18 AM

interesting point to note here: a Very large scale MIMO antenna is exactly what kind of radar antenna that can detect stealth aircraft in the air. (vaguely crypto but not really.) just an observation…

Nathan Myers • October 17, 2013 3:50 AM

This MIMO antenna farm brings to mind the Iridium satellite constellation. Considered as a phased array, its configuration is changing continuously, but predictably, and it’s hard to park receivers next to them. Likewise GPS, Galileo, GLONASS.

We may speculate that this is the real purpose for those systems, and that reliable navigation is just a side benefit and cover story.

Jay • October 23, 2013 9:32 PM

Well, I guess there’s a new way to get funding for VLBI radio telescope arrays…

Seriously though: If you have perfect knowledge of the transmitter’s position, receiver’s position, their relative orientations, and all the transmission paths between them – why not just use a laser? (Multiple beams and delay sensitivity, if you’re worried about taps.)

And if this MIMO system works without that perfect knowledge – then that sounds like a very large pool of equivalent keys…

Lambert • May 20, 2014 2:41 PM

What’s a ‘panic zero’? presumably some system for encryption without being able to see the key or plaintext.

Massive MIMO Cryptosystem

Comments

Leave a comment Cancel reply