Cross-stitch and Encryption
Made by Maggie Oates
What if cross-stitch could help encryption? When encrypting messages, recipients need to validate that a sender is, in fact, the person they say they are. To do this, the sender gives the recipient a long number generated computationally, called a key fingerprint. Then, the recipient gets a message with a fingerprint and manually compares the message and sender fingerprints, a tedious task. But what if the sender could give the recipient a cross-stitch instead?
Created: February 17th, 2018
When encrypting messages, recipients need to validate that a sender is, in fact, the person they say they are. To do this, the sender gives the recipient a long number generated computationally, called a key fingerprint. Then, the recipient gets a message with a fingerprint and manually compares the message and sender fingerprints, a tedious and difficult task. In one experiment testing the difficulty of key comparisons, between 1/5 and 1/3 of users failed to find differences .
If the keys do not match, there are three main scenarios that might be occurring:
In the 3rd case, impersonators often attempt to change the fingerprint only slightly (e.g., changing only one digit) so that the difference is even more difficult to find. As vulnerable populations such as activists and journalists often rely on this type of encryption, the impact of accidentally trusting an impersonator could be serious or even deadly.
As a result, there have been many attempts to improve the usability of fingerprints. Because the fingerprints are simple, static numbers, they can be mapped to other "spaces" to make fingerprint comparisons easier. For example, there are programs that map fingerprints to sentences, ASCII art, flags, random abstract graphics, and even unicorn avatars. The images below show examples of a unicorn fingerprint and the slowed-down process of mapping an ASCII art fingerprint.
In this project, I will build a similar mapping from fingerprint hashes to cross-stitch patterns. Why?
There are a few main tasks to completion:
Tasks in bold have already been completed or are ongoing.
To make the mapping from N large numbers to cross-stitch patterns, I could, in theory, design N different patterns and then manually map them (0000000001 → design 1, 000000002 → design...). But given that encryption requires very large numbers, this would be incredibly time-consuming. Instead, I want to define a smaller set of variables that can be randomly altered to generate a large set of designs. The simplest solution to this problem would be to simply randomly place single stitches on a square grid of size sqrt(N!). However, I wanted the patterns to look closer to traditional cross-stitch, so I needed to define "units" of cross-stitch patterns. I looked at samplers, existing patterns, and pixel art to identify common components. I ended by choosing the following variables to randomize:
Some image examples I drew inspiration from are below:
The strength of cryptography keys is defined in terms of entropy, roughly "how random" the keys are. Think about picking a colored ball randomly from a bucket full of balls. There are a few factors at play that determine how random picking a ball of a specific color is. If the bucket size increases and more balls are added, then the randomness also increases: so the volume of the bucket is one factor. However, another factor is how different the colors in the bucket are. No matter how large the bucket is, if the balls are all the same color, our randomness does not increase. These factors are called "dimensions". The size of each factor (e.g., 1 color vs 100 different colors) is called "cardinality". We can multiply them to find how big our random "space" is. Because computers use binary numbers, in cryptography, numbers are usually picked from a space that has a size equal to a power of 2. For that reason, we need to be able to map cross-stitch patterns to spaces that have the proper, computer-friendly size.
In the case of cross-stitch, we can think of the components outlined in step 1 as our dimensions. The cardinality is how many options of each component is available. For example, suppose our patterns had 2 flowers with 5 options for type of flower, to yield 2*5=10 different options. Alternatively, we could design our patterns to have 3 flowers and 4 flower designs, for 3*4=12 options. Here, each flower is a dimension, the cardinality is the number of flower types, and the space is the number of options. We can choose higher/lower dimensions and cardinality to yield different spaces. The tricky thing is, again, that our space needs to be a power of two. So this quickly becomes an interesting combinatorics problem to figure out how to pick cross-stitch shapes, colors, and layouts that multiply to yield the correct space. For example, suppose our cross-stitch design was k horizontal lines of specific colors. If we have n colors total, we need to solve how to find n and k such that they produce the correct computer-friendly size. The equation below formalizes somewhat the process to do so.
...So this step mostly involves designing equations and then begging WolframAlpha to do the math for me.
Knowing my components, dimensions, and space, I need to then translate that into code that generates images of patterns. To do so, I tentatively plan to use Python's TkInter package for image rendering. Here's some steps that will be involved in this process:
I'm really excited to generate the pattern for one of my actual public key fingerprints and complete it. To cross-stitch, I need to collect physical supplies:
I'd love to actually test it out by giving someone the finished cross-stitch and then send them an encrypted message.
Cross-stitch is the OG of pixel art.
As it relates to key comparison, there's something special about the deliberateness of cross-stitch that really appeals to me. When I send someone a crypto fingerprint, I am sending them an assertion of my identity. That usually happens with a few clicks of a button. With cross-stitch, the process of making and transferring my fingerprint is extended to hours or days of work. The physical, finished product is something that someone can physically hold, and even cherish. During the comparison process, a recipient is holding a product of great effort, a potent reminder to take as much care in comparing every stitch as the crafter did placing them.
(I swear I didn't set out to make my final project a computation problem, but somehow it always happens...)
 Tan, Joshua, et al. "Can unicorns help users compare crypto key fingerprints?." Proceedings of the 2017 CHI Conference on Human Factors in Computing Systems. ACM, 2017.
 Hsiao, Hsu-Chun, et al. "A study of user-friendly hash comparison schemes." Computer Security Applications Conference. ACSAC'09. Annual. IEEE, 2009.
 Anwar, Mohd, et al. "Gender difference and employees' cybersecurity behaviors." Computers in Human Behavior 69 (2017): 437-443.
Here are a few selected samples of skills learned in class.
What if cross-stitch could help encryption?
When encrypting messages, recipients need to validate that a sender is, in fact, the person they say they are. To do this, the sender gives the recipient a long number generated computationally, called a key fingerprint. Then, the recipient gets a message with a fingerprint and manually compares the message and sender fingerprints, a tedious task.
But what if the sender could give the recipient a cross-stitch instead?