Someone claiming to be a researcher from top Indonesian University published a new geofencing encryption algorithm in ResearchGate and people have been sharing this in LinkedIn without realizing the danger of this encryption.

You can see the full paper below:

There are so many hilarious things about the author and the calculation errors in the published paper, but we are not here to attack anyone. We are here to educate the public that encryption is no laughing matters. What if some developers copy paste this implementation (thinking that it must be secure because there is a paper for it)? Many innocent end-users will be impacted with leaked private/confindetial data. So, let’s not focus on the author, instead we’ll deep dive on why the encryption provided by IAST does NOT work.

Author Claims

1. He created new mathematical techniques so you could open a WebApp which will only decrypt a message when you are physically located on a specific area.
2. IAST-GeoFence decryption without being in the correct geofence requires polynomial time in the security parameter.
3. The I in IAST stands for “Irreversible” and IAST is Pre-Image resistant.

How to quickly find the flaw without even reading the paper?

This encryption uses location coordinate as part of the key. Intuitively we can immediately worry about whether the location claimed by the user is the real location of the user. From the description in linkedin post, the author never mentioned anything about how the user location is taken / verified, eventhough that should be the most important part of this whole operation.

Funnily enough, the description in linkedin post already gave away the flaw, as you can see in the circled part below. Having no backend for encryption is not something you should be boasting about, it is a flaw. Client-side verification in encryption is equivalent to not having any encryption at all. It is trivial for user to manipulate their location coordinate.

We can confirm our suspicion further by visiting the webapp the author showcased in one of the photo in the linkedin post. You can try it yourself here: https://iasttest.netlify.app/

Viewing the page source, we can immediately identify that the verfication of user location is being done on client-side.

        navigator.geolocation.getCurrentPosition(pos => {
          const lat = pos.coords.latitude;
          const lon = pos.coords.longitude;
          const dist = haversine(lat, lon, center.latitude, center.longitude);
          console.log(`Jarak ke pusat: ${dist.toFixed(2)} meter`);

navigator.geolocation.getCurrentPosition is a browser-only API exposed by the JavaScript engine. When called, the latitude and longitude are obtained entirely inside the user’s device, passed to the arrow-function callback, and then processed locally. No data is sent to or checked by a back-end server.

As a demonstration, we can go to developer options in our browser > More Tools > Sensors, and key in the MIT Great Dome coordinate. The WebApp will think that we really are at the MIT Great Dome, and then proceed with the decryption.

So, without knowing math, without even opening the paper, we can already debunk Author’s 1st Claim, because we can make the WebApp decrypt the message without being physically present at the required location.

Dissecting the math and implementation in the paper

Below is the schematic of the IAST-GeoFence Protocol as outlined in the paper. The flaws on the pertinent steps are highlighted in red.

Unauthorized decryption of the IAST-GeoFence

The most obvious issue with IAST-GeoFence is that it included the metadata, salt, and geocode (which was used to deterministically derive the key using HKDF) together with the ciphertext in the cipher_pkg.json. This is the same as encrypting a secret with AES and then sending the key together with the ciphertext to the recipient, so that the recipient can use that key to decrypt! Anyone on the internet can also use the key to decrypt the ciphertext.

import base64, hmac, hashlib, json
from Crypto.Cipher import AES

# from cipher_pkg.json which was made public for web integration
pkg = {
    "ciphertext": "3ihLSuNCzM/W4dU=",
    "tag": "dTl2ayqhshWTv1VGA46tBg==",
    "nonce": "sG8fXYYhjYSmz8B5l5hLiQ==",
    "salt": "lUYCdhbacnBd6dFy/ve5lA==",
    "geocode": "drt2yr27|50",
    "metadata": [7, 21, 19]
}

# re-implement HKDF-SHA-256 to derive key based on 3 input: digest, geocode, salt
def hkdf_sha256(digest_b, geocode, salt_b, length=32):
    prk = hmac.new(salt_b, digest_b + geocode.encode(), hashlib.sha256).digest()
    okm, t, c = b"", b"", 1
    while len(okm) < length:
        t = hmac.new(prk, t + bytes([c]), hashlib.sha256).digest()
        okm += t
        c += 1
    return okm[:length]

# build 6-byte digest as the source code does (big-endian 16-bit words)
digest_bytes = b''.join(d.to_bytes(2, 'big') for d in pkg["metadata"])

# key can be derived without even needing to guess the coordinate,
# because HKDF is deterministic, and all three values of 
# digest, geocode, salt are made known to the public
key = hkdf_sha256(digest_bytes, pkg["geocode"], base64.b64decode(pkg["salt"]))

# decrypting AES-GCM using the derived key normally
cipher = AES.new(key, AES.MODE_GCM, nonce=base64.b64decode(pkg["nonce"]))
pt = cipher.decrypt_and_verify(base64.b64decode(pkg["ciphertext"]),
                               base64.b64decode(pkg["tag"]))
print(pt.decode())

As we can see below, without even needing to guess the coordinate location, anyone who has the cipher package can easily decrypt the secret locally. When the code above was run, the secret used in the paper, which was “SahiraAlwin”, can be retrieved.

So with the PoC code above, we have debunked Author’s 2nd claim that decryption without being in the correct geofence requires polynomial time. We just decrypt the cipher in O(1) time without being at the required location or even knowing the coordinate.

Irreversible Alwin-Sahira Transform IS NOT IRREVERSIBLE

First of all, what is “irreversible” in the context of cryptography?

A one-way (irreversible) function needs to have two properties:

• Pre-image resistance (Given the output, nobody can figure out any input that produces it)
• Second-pre-image resistance (Given one input x, nobody can find a different input x′ with the same output)

IAST is NOT pre-image resistance, because we can easily find another input that produces the same output used in the paper, [14,18,21]

Note: The Auhor made a mistake in calculating the digit sum modulo m. Since m is 2**16, and the biggest possible value of digit sum will always be smaller than 2**16, the mod will not do anything. The final result of IAST in 2.3 Calculation Example should have been [14,18,21]

IAST starts with a list of whole numbers (the bytes of your plaintext). IAST outputs k words, each reduced modulo m. So, it will end with only three small numbers.

With the paper’s default k = 3, m = 2**16 the digest space contains: 2**16 * 2**16 * 2**16 = 2**48

If the input vector holds n 16-bit elements (they use 7 ASCII codes in the example, so we will take n=7 here) the input space is: 2**(16n) = 2**112

By the pigeon-hole principle at least: 2**112 / 2**48 = 2**64 distinct inputs share every single digest value. The bottom line is: far more different inputs than outputs ⇒ many inputs must collapse to the same digest. That alone proves the transform cannot be one-to-one, hence not “irreversible.”

Another way of looking at it is that, the digest output space is tiny, at 48 bits. A bruteforce to find collisions will take at worst 2**48 trials. One high-end consumer GPU (≈ 10**12 ops/s) reduces that to ~5 minutes. Not to mention the are still digit-sum and sorting clusters outputs, so the effective cost will definitely be much lower than 2**48.

Another issue is the non-uniform distribution. Digit-sum maps many integers to the same residue class (e.g., every number whose digits sum to 18 yields identical Dⱼ). Even from Table 1 in the paper, we can already see that the Digit Sum 18 was shared among the input v3 (104), v4 (105), and v7 (97).

The code below demonstrates how quickly we can find a collision, which are 2 different inputs that will yield the same tranformation output.

import math, itertools

# IAST parameters
ALPHA = (22.459, 5.043, 1.820)
def iast(v, k=3, m=2**16):
    scaled = [int(math.floor(x * ALPHA[i % 3])) for i, x in enumerate(v)]
    k_min  = sorted(scaled)[:k]
    digest = tuple(sum(int(c) for c in str(abs(y))) % m for y in k_min)
    return digest, scaled, k_min

# Step1: Calculate digest with Original vector
original = [83, 97, 104, 105, 114, 97, 97]           # “Sahiraa”
dig_orig, scaled_orig, sorted_orig = iast(original)

print("Original input  :", original)
print("Scaled values   :", scaled_orig)
print("Sorted values   :", sorted_orig)
print("Original digest :", dig_orig, "\n")

# Step2: Find a 3-byte collision
target = dig_orig
tries  = 0
for a, b, c in itertools.product(range(256), repeat=3):
    tries += 1
    if iast([a, b, c])[0] == target:
        triple = [a, b, c]
        break

print(f"Collision search: {tries} tries")
print("Collision prefix :", triple, "→", target)

# Step3: Extend with arbitrary large bytes
collision = triple + [1000, 1001, 1002, 1003]
dig_col, _, _ = iast(collision)

print("Full collision   :", collision)
print("Collision digest :", dig_col)

As we can see below, after just 2036585 tries, we can already find a collision.

Since it is possible to quickly find another input that produces the same output used in the paper [14, 18, 21], we have debunked Author’s 3rd claim that the IAST is irreversible and Pre-Image resistant.

Conclusion

What IAST-Geofence really achieves is just making an already proven encryption algorithm, AES-GCM, become vulnerable in its implementation. The Alwin-Sahira Transform does nothing to add to the robustness of the encryption, and it is NOT irreversible NOR Pre-Image Resistant. The client-side geolocation verification in the WebApp can be easily bypassed, enabling anyone not present in the required location to decrypt.

So please please please, don’t roll your own crypto and don’t endorse someone who does without fully understanding it first.

Social Media

Thanks for reading! Follow me on Twitter and LinkedIn