The Broken Keyboard

The problem in brief

A "secure" keyboard draws every keystroke as a 28 x 28 handwritten-looking character in a random style. After a coffee accident only 12 keys still work (letters A, B, E, F, O, I and digits 0, 1, 2, 4, 7, 8), and each one now corrupts its output in its own fixed way: it adds a fixed noise pattern (values in $[-25, 25]$), clips the result to $[0, 255]$, pastes it at the centre of a black 42 x 42 canvas and rotates the canvas by a fixed angle between $-30°$ and $30°$.

You receive 50 calibration pairs [original | corrupted] per key, 500 clean training images per key, 200 suspect images (some typed on the broken keyboard, some characters it cannot type) and 300 password images of 3, 5 or 7 corrupted characters side by side. Four missions: recover each key's angle (1) and noise (2), tell which suspects come from one of the 12 keys (3), and decide for each password whether most of its characters are letters or digits (4).

The statement is in Romanian; this is our paraphrase.

How you are scored

mission	metric	full marks	zero
1. angles (10 pts)	MAE over the 12 keys, in degrees	MAE $= 0$	MAE $\ge 1$
2. noise (10 pts)	MAE over the 12 noise matrices	MAE $\le 2.5$	MAE $\ge 10$
3. suspects (30 pts)	accuracy	$\ge 0.80$	$\le 0.50$
4. passwords (50 pts)	accuracy	$\ge 0.93$	$\le 0.50$

Between the bounds the points are linear, e.g. for mission 4: $50 \cdot \frac{\text{acc} - 0.50}{0.93 - 0.50}$. Mission 1 is unforgiving: any error at all costs points, so the angles must be found exactly. The organisers' labels are private: below, missions 1 and 2 are checked by how well our recovered model reproduces the calibration pairs, the classifier is validated on the 600 real calibration images, and mission 3 by a visual check of the suspects.

First look at the data

A calibration pair is an 84 x 42 image: on the left the clean character already padded to 42 x 42 (it occupies rows and columns 7 to 34), on the right what the broken key produced. Two things are visible at once: the rotation, and a faint speckle in the dark background near the centre of the corrupted image. That speckle is the key's noise, and it will turn out to be the most useful clue of the whole problem.

Why is the noise visible on the background? There the original pixel is 0, so after adding the noise and clipping, the pixel becomes $\max(N, 0)$: positive noise values survive, negative ones are clipped to black. Inside the strokes (value near 255) it is the other way round: negative noise survives and positive noise is clipped.

Mission 1: the angles

With the clean original $x$ and its corrupted version $y$ side by side, the angle can be found by brute force: rotate $x$ by every integer angle $a \in [-30, 30]$ and keep the one with the smallest mean absolute difference to $y$, averaged over 15 pairs. The noise is small and only covers the centre, so it barely disturbs the comparison.

Two details make the difference between "close" and "exact":

• Which rotation? We tried PIL bilinear, PIL bicubic, SciPy (orders 1 and 3) and OpenCV. They agree on the best integer angle, but only PIL bicubic reproduces the corrupted images almost perfectly (see mission 2). Its convention: a positive angle turns the image counter-clockwise.
• Integer or not? Refining with steps of $0.1°$ never moved the optimum away from an integer (the best fractional angle had the same error as the integer one), and the best angle is always clearly separated from the second best (mean error 0.8 to 0.9 grey levels against 1.2 to 1.8).

Result:

key	A	B	E	F	O	I	0	1	2	4	7	8
angle (°)	$-8$	$-30$	$+16$	$+5$	$-28$	$+10$	$+15$	$+9$	$-30$	$-27$	$-24$	$+10$

Mission 2: the noise, by inverting the forward model

The key idea: write down the forward model exactly, then fit its unknowns. For key $c$ with angle $a_c$ and noise $N_c$, the corrupted image of an original $x$ is

$$y = \operatorname{clip}\Big(\mathcal{R}_{a_c}\big(\operatorname{pad}(\operatorname{clip}(x + N_c, 0, 255))\big), 0, 255\Big),$$

where $\mathcal{R}_a$ is the bicubic rotation. Bicubic interpolation is linear in the pixel values, so $\mathcal{R}_{a}\circ\operatorname{pad}$ is a fixed $1764 \times 784$ matrix $M_a$. We build it column by column by rotating 784 "impulse" images (one pixel set to 1) in floating point. The outer clip is needed because bicubic interpolation overshoots slightly beyond 255 near sharp edges.

With 50 pairs per key, we know every $x_k$ and $y_k$, so we can estimate the 784 values of $N_c$ by minimising

$$\mathcal{L}(N) = \sum_{k=1}^{50} \big\lVert \operatorname{clip}\big(M_{a_c}\,\operatorname{clip}(x_k + N)\big) - y_k \big\rVert^2 ,$$

with Adam in PyTorch (800 steps, $N$ kept in $[-25, 25]$). The clipping is not a nuisance here, it is the right model: where a sample is clipped, the gradient is zero and that sample simply carries no information about that pixel, while the other samples (with other fonts, hence other stroke positions) do.

How do we know the model is right? The fitted model reproduces the 600 corrupted images with a mean squared error of 0.011 to 0.018 grey levels squared, which is the size of the rounding to integers. With bilinear rotation instead, the same fit leaves an error of 15 to 44: the choice of interpolation is not a detail.

The fitted noise then revealed two facts the statement only hints at:

• The "central zone" is the central 14 x 14 block (rows and columns 7 to 20 of the 28 x 28 image). Outside it, all estimates sit at about $-0.5$: the true noise there is 0, and $-0.5$ is a constant offset of our model (the generator apparently truncates rather than rounds somewhere). We subtract this offset and set the outside to exactly 0.
• The noise values are integers. After removing the offset, the estimates inside the zone are within 0.1 of an integer for half of the pixels, and roughly uniform over $[-25, 25]$. We round them.

Inside the zone, every pixel is covered by at least one unclipped sample for 11 keys out of 12 (key "1", a thin stroke, leaves 8 pixels that are always clipped and cannot be recovered). So the estimated noise should be essentially exact, far below the 2.5 MAE needed for full marks.

Missions 3 and 4: reading corrupted characters

A first baseline: a CNN trained on simulated corruption

Now that we know every key's transformation exactly, we can manufacture training data: push each of the 6,000 clean training images through its own key's forward model. A small CNN (five 3 x 3 convolution layers with batch norm, global average pooling, 13 outputs) trained for 8 epochs on these images recognises the 12 keys. We validate it on data it never saw and that come from the real generator: the 600 corrupted calibration images. Accuracy: 98.5 %.

For mission 3 we also need a class "not one of the 12 keys". We tried to provide negatives by rendering the other letters and digits with system fonts and passing them through random transformations. It did not work: the CNN called 98.5 % of the suspects valid, although about half of them are visibly other characters (K, m, N, H, 3, 5, 6, 9, ...). Printed fonts look too different from the handwritten style of the data.

The key idea for mission 3: check the key's fingerprint

A suspect typed on the broken keyboard carries the noise pattern of its key, rotated by the key's angle; an image from an external source does not. So for each suspect:

1. let the CNN guess which key $c$ it would be;
2. inside key $c$'s rotated 14 x 14 noise zone, take the dark pixels (value $< 45$, i.e. background);
3. compute the correlation between those pixels and the template $\mathcal{R}_{a_c}(\operatorname{pad}(\max(N_c, 0)))$, the speckle that key $c$ leaves on a black background.

The suspects split into two clear groups. Those with a correlation near 0 do not carry the fingerprint of the key they resemble; the others match it as well as genuine calibration images do. We call a suspect valid if its correlation is at least 0.22 (the valley between the two modes; only 3.8 % of genuine calibration images fall below it), or if its best correlation over all 12 keys reaches 0.35 (this rescues a valid character the CNN attributed to the wrong key). Result: 102 valid, 98 invalid.

Why does it work so well? A correlation over $n$ independent pixels has a standard deviation of about $1/\sqrt{n}$ when there is no real link. With $n \approx 85$ background pixels in the zone, that is about 0.11, so a correlation of 0.5 is a 4 to 5 sigma event. The fingerprint is weak only for very bold glyphs that cover most of the zone and leave few background pixels.

We have no labels for the suspects, so we checked the result by eye: on all 200 images, the images flagged invalid are, with a handful of exceptions, characters the keyboard cannot type, and the images flagged valid are A, B, E, F, O, I, 0, 1, 2, 4, 7 or 8. The doubtful cases (about 5) are bold or very thin glyphs such as an "8" or a "1" with a weak fingerprint. Our estimate is an accuracy of about 0.95, comfortably above the 0.80 needed for the full 30 points.

Mission 4: majority vote

Password images are 126, 210 or 294 pixels wide: exactly 3, 5 or 7 corrupted characters of 42 pixels side by side. Cut them into 42 x 42 tiles, classify each tile with the CNN among the 12 keys, count letters versus digits, and output the majority. Since the passwords have an odd length, there is never a tie.

A majority vote is forgiving: with a per-character accuracy $p = 0.985$, a 3-character password is wrong only if at least 2 characters are wrong and the errors flip the category, so its error rate is at most $3p(1-p)^2 + (1-p)^3 \approx 0.07\,\%$; and most CNN errors stay within the same category anyway (confusing O with 0, or I with 1, is the dangerous case). Two CNNs trained independently agree on 99 % of the passwords, which suggests an accuracy around 0.99, well above 0.93.

Results

mission	approach	check	estimated points
1	integer angle search with PIL bicubic rotation	best angle clearly separated, integer	10 / 10 (if the grader uses PIL's sign convention)
2, first try	fit with bilinear rotation	reproduction MSE 15 to 44	not usable
2	fit through the exact forward model (bicubic + both clips), zone, offset, rounding	reproduction MSE 0.011 to 0.018	10 / 10
3, first try	CNN with font-rendered "other" class	98.5 % of suspects called valid	about 0
3	CNN key guess + noise fingerprint correlation	bimodal scores, visual check about 0.95	30 / 30
4	CNN per tile (98.5 % on real calibration images) + majority vote	99 % agreement between two CNNs	50 / 50

Two honest caveats: mission 1 depends on the sign convention of the rotation (we report PIL's, counter-clockwise positive, which is also the convention of scipy.ndimage.rotate and of the generator we reverse-engineered); and the CNN's 98.5 % is measured on the calibration images, whose fonts may resemble the training fonts more than those of the passwords.

What to remember

• Reverse-engineer the generator when the data is synthetic. Writing the forward model down exactly (including interpolation type and clipping) turned two "estimation" missions into near-exact recoveries, and gave unlimited labelled training data for the others.
• A linear operator can be built by probing it with impulses, and then any differentiable model around it (here with clips) can be fitted with gradient descent in a few lines of PyTorch.
• Check your model by its residual. The drop from an MSE of 15 to 0.015 when switching from bilinear to bicubic was the proof that the model was right, and it exposed hidden facts (the 14 x 14 zone, integer noise).
• Open-set recognition is hard with a closed-set classifier. Instead of asking a CNN "is this some other character?", look for evidence that only genuine samples carry: here, a device fingerprint.
• Majority votes amplify a good per-item classifier: 98.5 % per character becomes about 99 % or more per password.