summaryrefslogtreecommitdiff
path: root/content/blog/kicad-mesh-plugin/index.rst
blob: df15933a1663c0e2254623376c281f7db7ef17ad (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
---
title: "Kicad Mesh Plugin"
date: 2020-08-18T13:15:39+02:00
---

.. raw:: html

    <figure>
    <img src="images/anim.webp" style="max-width: 20em">
    </figure>

Tamper Detection Meshes
=======================

Cryptography is at the foundation of our modern, networked world. From email to card payment infrastructure in brick and
mortar stores, cryptographic keys secure almost every part of our digital lives againts cybercriminals or curious
surveillance capitalists. Without cryptography, many of the things we routinely do in our lives such as paying for
groceries with a credit card, messaging a friend on `Signal <https://signal.org>`_ or unlocking a car with its keyfob
would not be possible. The security of all of these systems in its core lies on the secrecy of cryptographic keys.
Systems differ in what kind of keys they use, how often these keys are replaced and the intricacies of the cryptographic
operations these keys fit into but all have in common that their security relies on keeping the keys secret.

In practice, this secrecy has been implemented in many different ways. Mass-market software such as browsers or
messenger apps usually relies on some operating system facility to tell the computer "*please keep this piece of memory
away from all other applications*". While on desktop operating systems usually this does not provide much of a barrier
to other programs on the same computer, on modern mobile operating systems this approach is actually quite secure.
However, given sufficient resources no security is perfect. All of these systems can be compromised if the host
operating system is compromised sufficiently, and for organizations with considerable resources a market has sprung up
that offers turn-key solutions for all wiretapping needs.

In some applications, this level of security has not been considered sufficient. Particularly financial infrastructure
is such a high-profile target that a lot of effort has been put into the security of cryptographic implementations. The
best cryptographic algorithm is useless if it is run on a compromised system (from that system's point of view anyway).
One of the core cryptographic components in financial applications are smartcards like they are used as payment cards in
most countries nowadays. These smartcards contain a small, specialized cryptographic microcontroller that is designed to
be hard to tamper with. Though one of the design goals of the system is to reduce the amount of sensitive information
stored on the card, things such as copying of a card can only be hindered by making the chip hard to read out.

.. raw:: html

    <figure>
        <img src="images/modern_art.svg" style="max-width: 20em">
    </figure>

With smartcards being the means of choice on one side of the counter in electronic payments, on the other side of the
counter a different technology prevails. Attacks on payment terminals are bound to have much more dire consequences than
attacks on individual cards since one terminal might see hundreds of cards being read every day. For this reason, the
level of attack countermeasures employed in these terminals is a considerable step up from bare smartcards. While a
smartcard is made physically hard to tamper, it does not have a battery and it can only detect tampering once it is
powered by a reader. This allows for well-equipped attackers to use tools such as Focused Ion Beam (FIB) workstations to
circumvent the smartcard's defences while it is powered down, and then power up the card to carry out the actual attack.

The answer to this problem in electronic payment infrastructure is called *Hardware Security Module*, or HSM. An HSM is
similar to a smartcard in its function (cryptographic processing using keys that are meant to never leave the protection
of the HSM). The one major between the two is that an HSM has its own battery and is continuously powered from its
manufacture to the day it is scrapped. If the HSM looses power at any point in time, it uses a small amount of energy
stored internally to securely wipe all cryptographic secrets from its memory within a few milliseconds.

Being powered at all times allows the HSM to actively detect and respond to attacks. The most common way this is done is
by wrapping the juicy secret parts in a foil or a printed circuit board that is patterned with a long and convoluted
maze of wires, called a *mesh*. The HSM is continuously monitoring these wires for changes (such as shorts, breaks or
changes in resistance) and will sound the alarm when any are detected. Practically, this presents a considerable hurdle
to any attacker: They have to find a way to disable or circumvent the mesh while it is being monitored by the HSM.  In
practice, often this is no insurmountable challenge but it again increases attack costs.

DIY Meshes
==========

Throughout my studies in security research I have always had an interest in HSMs. I have taken apart my fair share of
HSMs and at this point, to understand the technology more, I want to experiment with building my own HSM. In last year's
`HSM basics <{{<ref "blog/hsm-basics/index.rst">}}>`_ post I have lined out some ideas for a next generation design that
deviates from the bread-and-butter apporoach of using a mesh as the primary security feature. Before embarking on
practical experiments with these ideas, I want to first take a stab at replicating the current state of the art as best
I can. State of the art meshes often use exotic substrates such as 3D plastic parts with traces chemically deposited on
their surface or special flexible substrates with conductive ink traces. These technologies will likely be too
cumbersome for me to implement myself only for a few prototypes, and industrial manufacturers will most likely be too
expensive. Thus, I will concentrate on regular PCB technology for now.

The idea of a mesh on a PCB is pretty simple: You have one or several traces that you try to cover every corner of the
mesh PCB's area with. To be most effective, the traces should be as thin and as close together as possible. To increase
the chances of a manipulation being detected, multiple traces can also be used that can then be monitored for shorts
between them.

While one can feasibly lay out these traces by hand, this really is an ideal application of a simple auto-router. While
general PCB autorouting is *hard*, auto-routing just a few traces to approximate a space-filling curve is not. Since I
am just starting out, I went with the simplest algorithmic solution I could think of. I first approximate the area
designated to the mesh with a square grid whose cells are a multiple of my trace/space size. The mesh will only be drawn
into grid cells that are fully inside the set boundaries. All cells outside or going across the border are discarded in
this step.

I decided to implement this auto-router in a KiCAD plugin. Though KiCADs plugin API is not the best, it was just about
usable for this task.

.. raw:: html

    <figure>
        <img src="images/kicad-mesh-outline.png" alt="KiCAD showing an irregular board shape with rounded corners and
        indents. In the middle of the board there is a footprint for a 4-pin surface-mount pin header.">
        <figcaption>The process starts out with the mesh shape being defined inside KiCAD. The mesh's outline is drawn
        onto one of the graphical "Eco" layers. A footprint is placed to serve as a placeholder for the mesh's
        connections to the outside world. This footprint is later used as the starting point for the mesh generation
        algorithm.</figcaption>
    </figure>

.. raw:: html

    <figure>
        <img src="images/grid-vis-plain.svg" alt="A vizualization of the grid fitting process. Over the mesh's irregular
        outline a grid is drawn. In this picture, all grid cells that are fully inside the grid are shown. Grid cells
        that overlap the mesh border are highlighted. Grid cells outside of the mesh border are not drawn.">
        <figcaption>A visualization of the grid fitting process. First, a grid large enough to contain the mesh border
        is generated. Then, every cell is checked for overlap with the mesh border area. If the cell is fully inside, it
        (yellow), it is considered in the mesh generation later. Cells outside (gray) or on the border (red) are
        discarded.</figcaption>
    </figure>

After generating the grid, starting from the place I want to connect to the mesh, I walk the grid's cells one by one to
generate a tree that covers the entire grid's area. To set the mesh's starting place I place a footprint on the board
(dark gray in the picture above) whose designator I then tell my script. The tree generation algorithm looks like a
depth-first search, except all checks are random. Depending on the level of randomness used at each step of the
algorithm it yields more or less organized-looking results. Below are five example runs of the algorithm at differing
levels of randomness with the cells colored according to their distance from the tree root. 0% randomness means that the
algorithm is going to try cells in forward direction first on every step, and only then try out left and right. 100%
means that on every step, the algorithm is choosing a new direction at random.

.. raw:: html

    <div class="subfigure">
        <figure>
            <img src="images/cells-0.svg" alt="a completely organized looking grid with spiral patterns all over.">
            <figcaption>0%</figcaption>
        </figure>
        <figure>
            <img src="images/cells-25.svg">
            <figcaption>25%</figcaption>
        </figure>
        <figure>
            <img src="images/cells-50.svg">
            <figcaption>50%</figcaption>
        </figure>
        <figure>
            <img src="images/cells-75.svg">
            <figcaption>75%</figcaption>
        </figure>
        <figure>
            <img src="images/cells-100.svg" alt="a completely random looking grid with cells aggregating into ireggular
            areas that look like paint splotches.">
            <figcaption>100%</figcaption>
        </figure>
    </div>

After I have built this tree like you would do in a depth-first search, I draw my one or several mesh mesh traces into
it. The core observation here is that there is only 16 possible ways a cell can be connected: It has four neighbors,
each of which it can either be connected to or not, which results in 2^4 options. If you consider rotations and
mirroring, this works out to rotations or mirrored versions of only six base tiles: The empty tile, a tile with all four
sides connected, a straight through, a 90 degree bend, and a "T"-junction—see the illustration below.

.. raw:: html

    <figure>
        <img src="images/maze_tiles_plain.svg" style="max-width: 20em">
        <figcaption>
        There are six possible tile types in our connectivity graph inside its square tiling. This graphic illustrates
        all sixteen rotations of these with how they would look in a two-conductor mesh.
        </figcaption>
    </figure>

After tiling the grid according to the key above, we get the result below.

.. raw:: html

    <figure>
        <img src="images/tiles-25-small.svg">
        <figcaption>
        An auto-routed mesh with traces colored according to tile types.
        </figcaption>
    </figure>

.. raw:: html

    <figure>
        <img src="images/traces-25-small.svg">
        <figcaption>
        The same mesh, but with traces all black.
        </figcaption>
    </figure>

Putting it all together got me the KiCAD plugin you can see in the screenshot below.

.. raw:: html

    <figure>
        <img src="images/kicad-mesh-settings2.png">
        <figcaption>
        The plugin settings window open.
        </figcaption>
    </figure>

.. raw:: html

    <figure>
    <img src="images/kicad-mesh-result-large.png">
    <figcaption>
        After runing the plugin, the generated mesh looks like this in pcbnew.
    </figcaption>
    </figure>

I am fairly happy with the result, but getting there was a medium pain. Especially KiCAD's plugin API is still very
unfinieshed. It is hard to use, most parts are completely undocumented and if you use anything but its most basic parts
things tend to break. One particular pain point for me was that after generating the mesh, the traces have been added to
the board, but are still invisible for some reason. You have to save the board first, then re-load the file for them to
become visible. Also KiCAD crashes whenever the plugin tries to remove a trace, so currently my workflow involves always
making a copy of the board file first and treating mesh generation as a non-reversible finishing step. 

`Check out the code on my cgit <https://git.jaseg.de/kimesh.git/tree/plugin/mesh_dialog.py>`_.

.. ::

    .. raw:: html

        <figure>
            <img src="images/grid-vis-plain.svg" alt="">
            <figcaption></figcaption>
        </figure>