6
$\begingroup$

I have two secret keys. One is a secret key generated by OpenSSL (primary secret key). Second key is generated by performing one way hash operation to GPS co ordinates and time parameters (geo secret key). Now I want to combine this two keys to be used for an AES encryption. I have two options.

  1. Encrypt twice by using two keys.
  2. XOR the two keys derive a single key and use it for encryption.

The first option will be bit expensive since there will be two encryption operations. Although the second option will be less expensive I am not sure whether it is secure or not. Will the second option make the finale encryption key vulnerable? Will it severely affect the randomness of the finale key in a way that it is not usable?

More details about my requirement: I want to decrypt a message successfully only when the device is in a specific location. So I am deriving a second key based on the GPS data. But location and time cannot be kept secret. So I need to know whether will it reduce the randomness of my finale key due to the XOR operation done between Primary secret key and Geo secret key.

Improve this question
$\endgroup$
5
  • $\begingroup$ Why do you want to use these keys? What are your goals? What threat are you trying to avoid? What are you trying to achieve? What bad outcomes are you trying to avoid? $\endgroup$
    – D.W.
    Oct 2, 2013 at 20:22
  • $\begingroup$ I want to decrypt a message successfully only when the device is in a specific location. So I am deriving a second key based on the GPS data. But location and time cannot be kept secret. So I need to know whether will it reduce the randomness of my finale key due to the XOR operation done between Primary secret key and Geo secret key. $\endgroup$
    – deltaaruna
    Oct 3, 2013 at 4:07
  • 2
    $\begingroup$ Yeah, that's not gonna work. Someone who is not physically at the specific location, but who knows where the specific location is, can still infer the key and decrypt the ciphertext. There's been academic work on this sort of problem (e.g., by Dorothy Denning), but it's a much harder problem than you seem to realize. $\endgroup$
    – D.W.
    Oct 3, 2013 at 4:54
  • 1
    $\begingroup$ Remembered me this xkcd algorithm: wiki.xkcd.com/geohashing/Main_Page $\endgroup$
    – woliveirajr
    Oct 9, 2013 at 13:57
  • 1
    $\begingroup$ For others: if you just want to combine keys with sufficient entropy, use a KBKDF (such as HKDF), if these keys together contain slightly too little entropy use a PBKDF (such as PBKDF2) with a high iteration count. If you have too little entropy for either scheme, you're scr\b\b\b out of options. $\endgroup$
    – Maarten Bodewes ♦
    Aug 16, 2014 at 17:25

5 Answers 5

Reset to default
7
$\begingroup$

You elaborated that your goal is to make it possible to decrypt a message successfully "only when the device is in a specific location".

Great goal, but yeah, well, the particular scheme you describe in your question ain't gonna work. Someone who is not physically at the specific location, but who knows where the specific location is, can still infer the key and decrypt the ciphertext. This is a fundamental flaw, and it's not something you can fix by sprinkling on a KDF or multiple keys. It doesn't matter how many keys you have or how you combine them. Sorry to break it to you, but your scheme is not secure, and it cannot be easily repaired. You're asking the wrong question: your whole approach is flawed.

There's been academic work on this sort of problem (e.g., by Dorothy Denning), but it's a much harder problem than you seem to realize, and the resulting schemes look very different. One has to find some source of unpredictable entropy that is visible to anyone who is at the specified location at the specified time, but that is not known or predictable to anyone else. That's very challenging.

For the state of the art in this area, see the following papers:

There may be more other work; I recommend that you do a literature search to check.

Improve this answer
$\endgroup$
5
$\begingroup$

I'm not really sure what your geo-location and time stamp key is really giving you above one well selected 128-bit key.

Let's say you're resolving the GPS co-ordinates to an accuracy of one metre. There are approximately $5 \times 10^{14}$ unique square metres of the Earth. We can probably safely exclude $2 \over 3$'rds of those metres on the basis that they're open ocean. This gives us approximately $2^{47}$ unique square metres to choose from. That's not large enough to adequately protect against brute-force.

The time portion is even more of a problem. An attacker who sees a message encrypted with this scheme knows the message was created before it was sent, otherwise causality is violated. Equally, it's safe to assume that no messages exist from a time before you asked this question on Stackexchange, as presumably you haven't built the cryptosystem yet. So the number of values to search here is very small indeed.

But perhaps the biggest problem with the scheme is that your position and time during an encryption/decryption operation is not a secret. Keys need to be secret in order to offer any security.

Your position and time can be readily obtained with sufficient precision to make brute-force a triviality.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Why wouldn't a slow KDF, like PBKDF2, stymie brute force attacks? $\endgroup$
    – Stephen Touset
    Oct 4, 2013 at 21:31
  • 4
    $\begingroup$ Suppose that each encryption operation normally takes one operation. Suppose you slowed it down by factor of a million. The apparent strength would still only be $2^{67}$ operations. In order to get it around $2^{128}$, you'd need to make it $2^{81}$ slower, which would make each crypto operation take longer than the universe has existed. $\endgroup$
    – Simon Johnson
    Oct 6, 2013 at 7:09
3
$\begingroup$

As others have said, a simple GPS co-ordinate won't gain you much entropy-wise because there's a limited likely range and it can be brute forced.

Having said that, depending upon the scenario you could use data from the location. For example, put a QR code on a wall, put a disposable wireless hotspot there, heck even use one of the USB dead drops that are so popular. You could alternately cook up something passively, e.g. a combination of barometric pressure, temperature, proportions of nearby buildings, but you don't have any guarantees that people couldn't find that information out remotely or that it would improve the entropy much.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Barometric pressure and temperature change all the time, building proportions are a bit hard to calculate on the spot. The other ideas seem good enough though. $\endgroup$
    – rath
    Oct 4, 2013 at 10:37
  • 1
    $\begingroup$ Sorry rath, I didn't explain myself well. The approach depends on whether it is a static message or a 2 way communication. Measurements may be useful if both parties have sensors in the same location and can communicate. Buildings, true advanced image processing may be required. Could be simplified by photographing shadows on the ground at a spot facing a certain direction at a certain time. $\endgroup$
    – David Cummins
    Oct 4, 2013 at 10:51
  • $\begingroup$ QR code is a great idea, but note that it does not meet requirements because you do not need to be present at the location to decrypt. Once you make a picture of it, you can keep using it forever. $\endgroup$
    – ArekBulski
    Mar 10, 2016 at 9:00
2
$\begingroup$

Note that the following answer does not directly answer your question, as you gave either the option to encrypt twice or to use XOR. But this question should show the best way of combining the key (seeds) to create a new key. Also note that this answer does not try and crypto-analyse your protocol, it's just a straightforward answer about how to combine to keys or sources of entropy.

You could consider to use a Key Based Key Derivation Function (KBKDF) such as HKDF over the concatenation of both "keys". In that way no entropy is lost, entropy that could be lost when the keys are XOR'ed together. This way you would only require a single pass to perform encryption.

It would also be easy to create additional keys, which you may require if you want to add message integrity and authenticity (using a message authentication code or MAC). You can do this by providing different "info" input parameters for each key.

This kind of functionality is the reason why KBKDF's have been defined.

Improve this answer
$\endgroup$
1
$\begingroup$

To directly answer your question, combining the two will always have a known level of security. If you stack the cryptographic operations one after the other, your security depends on the order in which they're stacked. If you encrypt using the location hash last, you are opening up an easily brute forced path to where the "primary secret key" is the only thing protecting your secrets.

From the question, I assume you're trying to tie a GPS to a device to decrypt a message successfully only when the device is in a specific location. This sets off a lengthy chain of issues. One is understanding that the precision of GPS is variable. Depending on many environmental things such as atmospherics, nearby metal buildings, construction, solar flares, jet streams, etc., standard GPS devices can easily be off by several meters. That means you need to build your solution to be fault tolerant, so the user will be successful when he is "close enough" to your target location. The way to do that is to reduce the precision of the coordinates, yielding coarser numbers. You will need to reduce Lat/Lon readings to no more than four decimal points of precision in order to make the system usable, and possibly fewer digits if you are permitting the user to report in from a larger area.

The reason precision is important is that it bounds the search space a determined attacker has. A four digit precision has a maximum value of 359.9999, or 3.6 million possible latitudes by 3.6 million possible longitudes around the globe, or 13 trillion (~$2^{44}$) possible locations. However, if your attacker knows anything about the device, he probably has an idea about the area in which it will be deployed. If your attacker knew the general area was somewhere within "the metropolitan area around Minneapolis, Minnesota", he might draw a bounding box from 45.2844/-93.6926 to 44.5865/-92.7782. That's only 6979 x 9144 possible locations, which is just shy of 64 million guesses. If you wish to compound that by stating your user has to be there on a specific day, that only multiplies it by the possible time range. If the attacker knows to within a month, that's still under two billion guesses.

A home-built computer using graphics cards for co-processors is able to perform 348 billion cryptographic operations per second. A slightly less resourceful attacker would take a bit longer, but he'd still figure it out quickly. Therefore, if your legitimate user knows the "primary secret key", he can test all two billion decryptions without moving an inch, and unlock your secret.

A slightly more secure approach would be to have your GPS-enabled box send the encrypted coordinates to a server over an authenticated connection. (Your server can also independently verify the time of day of the request.) That way you're breaking the problem into your two separate requirements: authentic person plus correct location. The benefit of using an on-line server is that you can detect and deny someone who is sending you thousands of guesses per second, and defeat a brute-force attack.

But if your legitimate user knows he is tasked with being in location X at time Y, he can always fake it (even if he can't make it.)

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.