Cross-stitch and Encryption

Intention

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 [1]. 

If the keys do not match, there are three main scenarios that might be occurring:

1. The message was garbled due to bad transmission (unlikely)
   
2. The message accidentally got sent to/from the wrong person
3. The message was sent from an impersonator (a Man in the Middle Attack)

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? 

1. Cross-stitchers are already skilled at comparing patterns.  Cross-stitchers are used to careful comparisons between a pattern and work in progress, so it's possible that they'll perform well when comparing fingerprints in a medium they're already skilled with. Moreover, the use of cross-stitch frames comparison as a careful process rather than a one-off action. 
   
2. Different people benefit from different representations.  For example, for language-based fingerprints, familiarity with the language can improve or decrease comparison accuracy. Different users prefer and perform best on a variety of fingerprint representations. [2]
   
3. Both cybersecurity and craft are gendered. In society's eyes, hacking, technology, and security are masculine. Cross-stitch is feminine. Women report much lower levels of self-efficacy for computer technology [3], which translates to women using cybersecurity tools less, and adjusting their web behavior to avoid risk.  Re-framing security may help bridge that gap.

Process

There are a few main tasks to completion:

1. Identify cross-stitch components that are suitable for mapping.  
2. Map those components to the suitable range of numbers.  
   
3. Implement the mapping & rendering in code.
4. Do the cross-stitch.

Tasks in bold have already been completed or are ongoing.

1. Identifying cross-stitch components  

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:

• Border style
  
• Square components - Flowers, hearts, etc
• Colors
• Position of components

Some image examples I drew inspiration from are below:

2. Mapping components to numbers

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. 

3. Implement the mapping & rendering in code.

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:

1. Be able to generate a background grid
2. Take images of components (from step 1) and manually change them into bitmaps
3. Define scaling and recursion logic for each component so they can be adjusted nicely for different grid sizes.
4. Write color logic
5. Section off bytes for each dimension to define number ↔ component mapping . Do some bit twiddling. 
6. Put it all together in a function that takes a hash, entropy, list of possible colors, and spits out an image of the pattern with a key of colors

4. Do the cross-stitch

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:

• embroidery hoop
• tapestry needle
• embroidery floss
• scissors
• printed fingerprint pattern
  

I'd love to actually test it out by giving someone the finished cross-stitch and then send them an encrypted message. 

Reflection

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...)

References

[1] 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. 

[2]  Hsiao, Hsu-Chun, et al. "A study of user-friendly hash comparison schemes." Computer Security Applications Conference. ACSAC'09. Annual. IEEE, 2009. 

[3] Anwar, Mohd, et al. "Gender difference and employees' cybersecurity behaviors." Computers in Human Behavior 69 (2017): 437-443. 

Other Resources:

• Wikipedia - Public Key Fingerprint
  
• Tyler Cipriani's excellent blogpost explaining fingerprints and visual fingerprints 
  
• Wikipedia - PGP word list is an easy-to-understand example of mapping from numbers to words

Sample Book

Here are a few selected samples of skills learned in class.