avadacatavra's blog

Intersectional Security

What do I do?

Sit around and pet cats all day? Yep.

When we’re talking about work though, I’ve started calling what I do intersectional security. It makes me feel fancy, but more importantly, it represents my opinion that the most interesting problems in security happen at the intersections with other domains.

What is it?

Currently, I’m interested in the intersections between Mixed Reality and security/privacy. What do I mean by this? Well, it turns out that there are unique considerations in MR that have an impact on how we approach even basic security problems. For example, what does traversing a link immersively look like? On the 2D web, browsers have indicators to show you where the link is going and if you can trust it. These indicators are rendered by the browser itself, not the page, so you know that the content isn’t being spoofed. However, we don’t have a browser chrome in an immersive web browsing experience, so what is a 3D analog to this? (If you have ideas, let me know)

It’s important for us to embrace the idea that security is an interdisciplinary domain. If you have great crypto, but a terrible UX that leads to users skipping security features, then you aren’t providing a very secure experience. This also implies that everyone is responsible for security (and privacy), versus delegating that responsibility solely to specific engineers.

Previously, I’ve explored applying machine learning to problems in cryptography. And who knows what I’ll end up doing next—that’s the best part of working in unique domains. Every day brings interesting challenges.

Oh hey 2019

I realize I’m late to the party. I still haven’t sent out my 2018 holiday cards (more on that later). My goals for the first half of 2019 were due today, which always triggers an existential crisis for me.

2018 ended up being pretty transitional for me–I joined the Mixed Reality team at Mozilla to work on privacy and security (while still working on Servo). It takes time to jump into a new role, particularly since I’d only put a VR headset on once before (at an Oculus demo at GHC2014). At the end of the year, my husband and I found out that we’d be moving from the UK, where we’ve been living for nearly four years, back to the US…and we had two months to execute the move.

We leave on Sunday. So far, in 2019, I’ve spent a week in California attending RWC, two weeks in New Zealand (speaking at LCA), two desperate weeks of cleaning/packing, a long weekend in Bruges and Brussels, and finally a week to say goodbye to the town I’ve come to love. It hasn’t left much time for retrospection, so I’m going to focus on what’s next.

Career

This is purely about my personal goals–not my goals for Firefox Reality/Rust/Servo as projects:

  • Privacy experiments with FxR
  • Write an RFC for Rust
  • Leadership/management training
  • Write an academic paper
  • Write a series on ethics in emerging tech
  • Write a chapter (for a friend’s project) on secure programming in Rust

Skills

Inspired by my friend, edunham, I considered the skills that I care about right now.

Some programmers might notice that there’s a strong emphasis on ‘soft skills’ here. I’m most effective when I work with others. Over the past year, I’ve realized that I’ve become pretty isolated, and it hasn’t been good for my mental health. It’s also really important for me to communicate better about the work that’s being done in the formal verification and unsafe code guidelines working groups.

Personal

It’s been a stressful time. I’d like to get back to taking care of myself, exercising, and sleeping.

Financial

Moving is expensive…

  • replenish savings after the move
  • have at least 1x my salary saved for retirement

(besides…you know, having to find a house and cars…)

Miscellaneous

  • Do a 30 day yoga challenge
  • Be able to do a pull up
  • Visit friends I haven’t seen since moving away <3
  • Throw a housewarming party!
  • Embrace inbox0
  • Send out my 2018 holiday cards before June 😂
  • Get involved with a charity/foundation

We Live in an Ocean of Air

I visited London last week to give an informal introduction to the work I’m doing with Mixed Reality privacy at the Mozilla London office. Luckily, this magically coincided with the office’s holiday party (imagine that…)

Tickets are timed entry—while you wait, you can watch others moving around in the experience and watch (a much more limited version of) the virtual environment on a screen. When it was my turn, I entered a small vestibule with 5 others (including my husband), where our “host” explained that we would put on a backpack that held a computer hooked up to a VR headset. Instead of holding controllers, they wrapped controllers around the wrists. Then, I put the headset (HTC Vive) on, they clipped a heartbeat monitor on my earlobe, and put headphones on.

They warned us that if anything went wrong or we felt ill, we should just lift the headset and they’ll be over to assist.

There were a few basic elements to the installation: a video/3D environment, immersive elements generated during the session, and sound. The world was focused around an ancient sequoia tree—I won’t spoil it—then morphed into a much more abstract environment. Overall, the experience was meditative, focusing on your breath and allowing you to visualize how your breath is released into the environment around you. A CO2 sensor recorded and transmitted information about exhalations, which was then incorporated into the shared immersive world.

I found it particularly interesting how they augmented the virtual world by incorporating data extracted from the physical world. Infrared sensors detected others in the space and created red blobs to prevent you from walking into others. This was…not always successful (I also have issues with depth perception, so that didn’t help). It created both an isolating feeling and a weird sense of togetherness. Isolating, because you can’t really interact with the others in the space (and when I called out to see if it’s my husband I just walked into, I couldn’t hear a response), but together, since you’re not just interacting with your breath, but everyone’s. It was particularly interesting when I reached for Ricky’s hand. In the virtual world, our hands met much sooner than they did in the physical world. I noticed some people walking around hand-in-hand with their companions, looking desperate to maintain that contact. It would be particularly interesting to see a similar experience on a platform like Hubs.

After some time, the virtual world became much more abstract. The floor dropped away and you were left in a space completely without boundaries (until you approached the boundaries of the actual room when the room grid showed up to tell you not to walk into a wall). This was particularly uncomfortable/disorienting for me, and I found myself focusing strongly on the sensation of my feet on the ground. As a work of art, I can appreciate the feelings of discomfort, but I think we should keep in mind that VR affects the physical body much more strongly than most other digital mediums. I didn’t feel the need to take my headset off, but I did need to pause for a bit.

Overall, I enjoyed the installation and would recommend it. You can book tickets here (£20). You do need to book ahead, because they only have a limited number of headsets.

I had discussions about the technical details and data collection both before and after the experience with the hosts/technicians (because that’s apparently what I do now). I am excited to see mixed reality as an art medium. At the same time, any immersive art also needs to consider the privacy aspect of the medium. Even if that’s not the primary intent of the work, data collection and privacy are fundamental to any MR experiences and deserve to be approached thoughtfully and respectfully.

For anyone who is unfamiliar with the privacy concerns associated with mixed reality, here are some potential risks:

  • tracking gaze in a virtual world can reveal whether a person has ADHD or autistic characteristics and indicate sexual orientation/attraction
  • devices analyze the way we move in a virtual space to enable physical/virtual interactions. Interactions like head/body movements (including gait) can be used to identify individuals
  • any biometrics (like heart rate/breath) can reveal information about underlying health conditions
  • we know that VR can be used therapeutically; however, this implies that it could also induce very negative physical/mental/emotional consequences (this hasn’t been studied because we’re not going to try to induce PTSD via VR for obvious reasons)

After I took the headset off, I though about how fascinating it would be to look at heart rate data, the prerecorded video, and the breath simultaneously. Did my heart race when the ground disappeared? What’s the difference in my physiological response compared to someone experiencing this for the first time?

Mixed reality provides a new way to experience the universe. Art has a unique ability to inform and educate, and I encourage everyone interested in working in the space to consider how we can convey both the joy of immersive experiences and the complex questions of biometric data collection and use.

My recommendations for immersive installations:

  • be clear about the data that can be collected by any devices used
  • if you are collecting data, state this upfront, as well as your plans for using the data (also address if the data is processed locally or sent elsewhere)
  • keep in mind that just because you don’t necessarily link identities to data doesn’t mean the data is anonymous

The worst case scenario for me is that we become accustomed to simply putting immersive tech on and not thinking about the privacy implications. On the flip side, I am (I swear) an optimist about immersive technology, so I don’t want our fears and concerns to stop us from engaging in VR/AR. There’s a balance that we can find, but only if we openly and proactively have ongoing discussions.

At the end of June, Mozilla’s amazing D&I program manager (and one of my fav people ever), Lizz Noonan, came to London for the Women of Silicon Roundabout conference. The best way for me to describe it would be “a more enjoyable Grace Hopper.”

Foxy was the most popular Mozillian at our booth

Then she visited Yorkshire and we went sightseeing!

Why I like “Women in Tech” conferences

I attend both academic and industry conferences—sometimes speaking, sometimes at a Mozilla booth, always with time to wander around. My favorite pastime is to look around the room I’m in and count the number of women and/or PoC1 there—usually this requires only one hand, sometimes two…never more. I’ve looked around a room and wondered why I’m even there.

It’s refreshing to look around and see people who aren’t men (I love you, but sometimes I want to spend time with other genders too!). Sometimes, non-men even have different perspectives and ways to approach problems that are really interesting!

There’s a talk I attended at GHC in 2014 from Jo Miller that has stuck with me. It was about office politics. At the time, I’d just left an internship with some… weird dynamics that I hadn’t been equipped to handle. Since then, I’ve managed to work in even more toxic environments, but I’ve been able to understand and work within them more effectively (while also making my way out of there because shitty work environments suck). The talk focused on identifying your strengths and relationship structures within the environment, then positioning yourself for success given that. Sitting around a table with others who have experienced the same problems is empowering! Trading strategies for getting your ideas heard or managing conflict is helpful!

ALL THE STICKERS

That said, I have some pet peeves. Yes, I want to hear origin stories, but honestly, not every talk needs to be about “My career as a woman in tech.” My favorite talks are usually the ones where someone talks about cool technology and they just happen to be a woman in tech. Also, no, I don’t want nail polish swag. Portable wine glass swag? Yes. Nail polish? No. Finally, if I am the only woman there, yes I care about diversity. No I don’t have any clue how to get more women involved aside from this2:

Don’t be an asshole.

My strong opinions about Grace Hopper

I’ve been to Grace Hopper twice (2014 and 2017), both as a student and with Mozilla. For comparison, let’s look at the attendee numbers:

  • GHC 2014: 7830
  • GHC 2017: 18000+
  • WSR 2018: 4000+

The first time I attended, I had a great time. The second…well, let’s just say the swag was good. There’s a huge difference between 8000 people and over 18000—I understand that there’s a huge demand, but (IMO) it’s just too big now. It’s…not manageable. There are definitely things that GHC gets right—scholarships, childcare, nursing mothers’ room to name a few. However, the quality of my experience as an attendee plummeted from 2014 to 2017.

The Recruiting Booth One of the great things about GHC is the students. However, that also means that the career fair is more geared towards internships and entry-level positions. There are mid-career talks, but it’s really not a focus of the career fair.

This corresponds with something I hear about a lot—how can we get more women in tech. In my experience (and others), we need to work on how we can get women to stay in tech.

From a recruiting booth point-of-view, I enjoy having fewer, but more productive, conversations, rather than feeling swamped by a line of people trying to trade resumes for swag.

But also, there’s great swag there.

The Talks It’s…really hard to get into talks at GHC now. You have to queue and wait for people to leave the room for more to be allowed in… and if people don’t leave between talks, then you’re out of luck (on the flip side, you also run the risk of losing your seat if you need to pop out of the room briefly).

Once I got into a talk…I was not impressed. That said, the problem could have been the subset of talks I made it into. It’s great that there are so (so, so, so) many talks, but pretty useless for my professional development if I can’t get into them.

The People Obviously, there are thousands of brilliant women (and others) at GHC. However, when you have an event of this size, it’s just a mob. I didn’t find myself organically running into people and having spontaneous interesting discussions. Honestly, it was so overwhelming, that by the end of the day I just wanted to hide out with my coworkers, not socialize and meet new people.

Women of Silicon Roundabout

Ok, back to the reason I’m writing this. Attending WSR reminded me a lot more of the 2014 GHC that I loved attending. I was able to attend talks—even just poke my head into sessions and listen for a few minutes.

In particular, I enjoyed being able to run into people from sessions I’d attended, booths I’d visited, or even finding people from meetups I’ve been to. It was easy to find a quiet space to grab coffee and chat about projects, common experiences in the workplace (nearly every woman I speak to has a workplace harassment story—not necessarily sexual, but always demoralizing), cats, etc.

There were a lot of non-US attendees (I mean, it was in London), which was refreshing. It made me think—what if instead of one ridiculously massive conference, there were a few smaller ones geographically distributed?

Negatives: I didn’t love the location. It’s not the easiest to get to (although I stayed in a hotel attached to the ExCeL, so I shouldn’t complain), and there’s just not a lot of food options outside the conference center. Realistically though, there’s only so many places in London that can fit that many people.

While I liked the layout of having session spaces ring the booth area (it was easy to wander around and listen to interesting topics without having to trek across the conference center), it was very loud. Very. Loud.

Miscellaneous:

The tech scene in London is way more finance focused. Like. Way more. And they dress up a lot more (although that’s common in my experience as an American expat in the UK—we are insanely casual in comparison). I can’t even imagine coding in jeans all day, let alone a pencil skirt. I’m firmly in team yoga pants—my coworkers can confirm that I always end up sitting on the floor doing weird yoga things while coding.

Also, there was a massage booth across from the Mozilla booth. Highly recommend.

Overall: I’d go back next year

I did not get to take Foxy home

Talks I enjoyed

The talks I attended were all in the emerging tech track which had a diverse set of topics and was conveniently located.

Making Pain Fun Using Virtual & Augmented Reality I’m still a bit dubious that pain is fun, but I’m excited to see more applications of MR than gaming. The premise is that pain medication addiction is rampant and we need alternative pain therapies. And it works.

How Tech Companies can not just do Good but Stay Good

People (both workers and users) aren’t just motivated by money, but also mission. Every company starts out with some sort of purpose, and these are often related to a social mission; however, as the company grows, mission can get lost. Google founders famously wrote “Don’t be evil. We believe strongly that in the long term, we will be better served…by a company that does good things for the world even if we forgo some short term gains.” As the company grows, how can you ensure that your company doesn’t become a corporate behemoth that cares only about profit? The speaker argued that you can have both profit and purpose, and it comes down to having that be integral to your business model and culture. It seems obvious, but when companies do it wrong, they end up looking artificial.

AI For Good: Fact of Fiction

I really enjoyed this talk–so often you hear people talking about replacing humans with AI, when the real strength lies in combining human intelligence with machine computation. Machine learning shouldn’t be a complete black box to the people acting on its results. Machines are great at running algorithms and large scale computations. Humans are great at synthesizing results and making informed, educated decisions. By combining these strengths, you can make users more efficient and help them recognize their cognitive biases–computers aren’t a substitute for people. Takeaways:

  1. Display the criteria that generated the results. What features led the algorithm to this conclusion?
  2. Identify data sources involved in the making a decision (highlight both included and excluded sources)
  3. Instead of using AI to filter out results, use it to suggest more. Discourage confirmation bias from top hits.

Blockchain Talks

Full disclosure: I didn’t attend any (because I didn’t want to). I’m fairly uninterested in blockchain (partially because I’m sick of people saying they’re interested in “crypto” and then talking about blockchain). Apparently blockchain is going to Solve Every Problem Ever.

  • How Blockchain Technology can Create the Evolution of Industries
  • Making Blockchain Work for Women
    • Abstract: “..the vast majority of crypto holders are men, but because of how the technology actually works, women are in a unique position to leverage blockchain to launch businesses, build rich reputations, and gain access to capital and power”
    • Ok, so I’m pretty sure blockchain works the same for men and women…and also that women have been systemically denied access to capital and power for centuries so…
    • Theory-time: Satoshi is a woman and published under a pseudonym so people would actually take her work seriously
  • Ending Workplace Harassment with Blockchain Technology
    • Abstract: “The role that blockchain tech can play in providing employees and employers innovative solutions to mitigate the problem. Blockchain technology presents a unique opportunity for both employees to record and report harassment like never before.”
    • Can’t see any way this could go wrong…
  • New Kid on the Block-chain
  • How Lending and Borrowing Provide New Opportunities for the Cryptoasset Market

Here are some “crypto3” talks I’m thinking of proposing4:

  • Using blockchain to solve the two-state problem
  • Crypto for non-binary people
  • Blockchains for determining if P = NP
  • Proof of work: encouraging managers to leverage blockchain for remote workers
  • Universal healthcare with blockchains
  • Climbing the blockchain ladder to success
  • Blockchain: recruit 10 friends and you can make millions running GPUs in your home
  • Suing people who steal your talk ideas with the blockchain in the cloud

1: These are almost always disjoint sets 2: I still don’t know why I went into CS and sometimes question how long I’ll stay 3: Not crypto. Crypto is short for cryptography. End of story. 4: I’m not. I will never.

OPLSS

24 Jul 2018 | View comments

OPLSS (A Review Partially Told in Gifs)

I recently returned from the Oregon Programming Languages Summer School, which was two and a half weeks of trying to smush a ridiculous amount of knowledge into my brain.

I decided to attend OPLSS because I would read these PL papers…and be completely confused. They were completely indecipherable to me. I’ve revisited some of these papers since getting home and I already understand so much more. Some main takeaways for me:

  • -calculus isn’t as terrifying as I thought
  • I have a lot of bedtime reading, starting with PFPL
  • There’s a language to talk about languages (aka the entire Foundations week)!
  • Types are specifications of behavior…and specifications are programs (see Computational Type Theory)–I can’t honestly say that I’ve processed anything from these lectures yet…

I was pleasantly surprised that I’ve had exposure to some terms and concepts just by using Rust. Overall, it was a great experience. I’m glad to be home (not so glad to work through my Github notifications and email). I appreciate the exposure to all of these PL concepts that I wouldn’t have been aware of otherwise, and I can’t wait to dive in more.

Stay tuned—I’m finishing up a few things that are stuck in my backlog (looking at you performance metrics), then I’m hoping to dive into some more work on formal verification.

A huge thank you to everyone involved in OPLSS—organizers, lecturers, participants—it was a pleasure to meet you all, and I hope to collaborate/run into you again someday!

Highlights

Location: Aside from the heat wave (and no A/C), Oregon was great. There’s maybe a bit too much nature for a dedicated indoorswoman like me, but overall, highly recommend. Specifically, Eugene has a wonderful store called Hirons that is simultaneously indescribable and also capable of fulfilling your every need. I bought allergy medication, a pineapple cup, and a swan floatie named George1 there.

People: it turns out that there are a lot of brilliant and lovely people doing PL research (And if any of you want to do Rust-related work, hmu)!

Participant Talks: Some nights, we had informal participant lectures, where anyone could share their research

Events: I had the pleasure of meeting Bob Harper—with a balloon that said “Die Already” and a shiny birthday tiara. It was literally the first time I’d ever met him. OPLSS hosted a surprise birthday party for Bob, and I somehow ended up organizing and greeting him. At the aforementioned Hirons, Zena and I acquired some balloons with questionable messages (“Happy Birthday–I hate you,” “Die Already,” “Grow Up,” “You’re Old,” etc.) for decor—that’s how everyone wants to be greeted, right? With a stranger holding a tiara and a mean balloon?

##


Selected Topics and Resources

Parallel Cost Semantics and Bounded Implementations

Session-Typed Concurrent Programming

Algebraic Effects and Handlers

Computational Type Theory

Game Semantics

There were many more topics (I haven’t even included anything from the week of Foundations of PL)–you can see all of the details here. My notes are…scattered around my computer, notebook, and iPad, because I kept breaking things, so I recommend checking out participant notes.


Rust Specific

Aaron Turon gave a talk about (PL-heavy) open research projects in Rust, so I’ll spread the word here too:

  • Chalk: describe Rust trait system in terms of logic
  • Polonius: model the borrow checker
  • Const-dependent types: there’s work on both the compiler and in Chalk—pop into #wg-traits on Discord to find out more

1: Sadly, George got locked in the room across from mine. Some UO freshman might have a fun surprise at the beginning of the semester.

Welcome back to part 2/n in my ‘hey look at the cool things that happened at RWC’ series.

Levchin Prize

Since 2015, the Levchin Prize has been awarded at RWC. So far, each year there’s been one individual recipient and one team recipient. This year, it went to Hugo Krawczyk (he created HMAC!) and the OpenSSL team (for dramatic improvements to code quality).

I can attest to the improvements to the quality in OpenSSL. A few years ago, part of a final in school was to trace some OpenSSL code. I love tracing code, and it had me jumping all over the place until I couldn’t open any more vim buffers (only a slight exaggeration). It’s much less awful today.

More importantly, the trophies are awesome. They’re based on a ‘cryptex’ and a wheel cipher. There are 7 rotating disks, and when they’re aligned correctly, the trophy opens to reveal an inner chamber. No clue what’s in it.

Side-channel mitigation – Olya Ohrimenko

Azure

Azure is Microsoft’s cloud computing platform. They’ve integrated confidential computing so that when data is being processed, it’s in a Trusted Execution Environment (TEE). When the data is at rest, it’s encrypted (as far as I can tell), but processing encrypted data is really inefficient (and not always possible). This presents a problem for cloud users with sensitive data–they have to protect the data, but they can’t simultaneously use it and ensure privacy protections.

Microsoft currently supports both software (Virtual Secure Mode) and hardware (Intel SGX) secure enclaves, and is working to make more available.

In particular, this talk addressed information leakage through memory accesses (she explicitly was not addressing Spectre/Meltdown). Consider a binary decision tree where all of the data is encrypted. Although the data is encrypted, you can still observe when memory is accessed and where. If you then do multiple traces, you could possibly reverse engineer the tree content.

That’s…not good–imagine that decision tree is a diagnostic tool, where the nodes contain your medical information. Now anyone who saw those memory accesses knows that you have Lupus (do you not spend your Saturday nights looking at cloud memory accesses?)! As with other side-channel flavors, you need some sort of ‘secret-independence.’

Memory side-channel mitigations

A naive approach is to insert dummy accesses into the code, but this is ad hoc, and still might leak data. Instead, you want to use a traditional, game-based security proof. This resulted in an idea called ‘data-obliviousness.’ Informally, this means that any algorithms shouldn’t branch on secret data. More precisely

We specify public parameters that are allowed to be disclosed (such as the input sizes and number of iterations to perform) and we treat all other inputs as private. We then say that an algorithm is data-oblivious if an attacker that interacts with it and observes its interaction with memory, disk and network learns nothing except possibly those public parameters. - USENIX paper

The talk mentioned four mitigation techniques:

  1. Data obliviousness
    • isolate computations in private memory
    • attacker can see addresses that go in/out, but not how the content is manipulated
    • limited private memory (for example, max 2kb in registers1)
  2. Explicit private memory
    • operate on registers directly in assembly
    • IMO, assembly should not be the goto option for side-channel mitigation
  3. Intel TSX
    • initially developed for concurrent data access
    • side effect: if data is evicted from the cache, the transaction aborts
    • can be used to turn caches into private memory 2
    • data becomes part of the read set of the transactions; therefore, if the attacker tries to evict it from the cache, the transaction aborts
    • cache misses can’t happen, so caches become private memory * size limitations
  4. Oblivious RAM (ORAM)
    • A more general solution to the problem, can be thought of as a proxy
    • hides which addresses are accessed and how often, but not the number of requests
    • data solution only, not code

But, back to the point–the talk was about data oblivious algorithms. They wrote data-oblivious algorithms for SVMs, matrix factorization, decision trees, neural networks and k-means clustering. Then, they ran oblivious and non-oblivious versions using SGX enclaves for decryption and processing. They validated the data-obliviousness by collecting traces at cache-line with Intel’s Pin tool.

A quick summary

Performance results

The following table (from the USENIX paper) shows the overhead when compared to a baseline the processes the data in plaintext without SGX. Both the oblivious and non-oblivious versions use SGX protection and encryption.

Algorithm non-oblivious data-oblivious
K-Means 1.91 2.99
CNN 1.01 1.03
SVM 1.07 1.08
Matrix factorization 1.07 115.00
Decision trees 1.22 31.10

There are a few quick conclusions from this chart:

  • using SGX and encryption doesn’t add significant performance overhead
  • some algorithms are already predominantly data-oblivious (CNN, SVM, K-Means)

One thing to note is that these are not state-of-the-art implementations, which might use data-dependent optimizations. But it’s neat to see that you can harden machine learning against data leakage with much more reasonable overheads than previous work.

Microsoft is calling this their ‘Always Encrypted capability.’ I take issue with this, because it’s not always encrypted–it’s just that it’s only decrypted and processed in an enclave. That’s not to say I have any better suggestions…but I’m opposed to misleading nomenclature like this. I’ve heard far too many talks that claim end-to-end encryption via TLS to think that a phrase like ‘Always Encrypted’ is a good idea when decryption is called at some point. While secure enclaves are great tools, they aren’t infallable.

I admit that The Cloud isn’t my favorite thing to talk about, mostly from dealing with people who think that it’s a magical way to make everything work, but I really enjoyed this talk. I was intrigued by the machine learning examples cited and noticed that they’ve applied for a patent on the technique described in the talk. I foresee more similar papers joining my TODO stack

1: SGX private memory is limited to registers

2: in very brief pseudocode: xbegin(); load_sensitive_code; load_sensitive_data; run_algorithm; xend();

Welcome back to part 3/n where I try to figure out what hapens after the quapocolypse! Quantum-pocalypse?

Post-quantum signatures - Melissa Chase

If you don’t already know, a sufficiently powerful quantum computer will be able to efficiently factor numbers and compute discrete logarithms. This breaks…everything (or at least public-key-everything). Currently, quantum computers can only handle a few q-bits, so we don’t have to worry about this, right? Wrong. Crypto is hard. And it takes a while.

Since the underlying assumptions we’ve relied on in the past will no longer be hard, what will be hard? Some proposed quantum hard problems:

  • lattice-based problems
  • supersingular isogeny Diffie-Hellman
  • code-based problems
  • multivariate polynomial problems
  • symmetric key primitives (or at least, we haven’t thought of a way to attack better with a quantum computer)

This talk is concerned with designing a PQ signature scheme using these symmetric key primitives. Wouldn’t it be nice if we could reuse something we already have?

Also, I get super bored with Prover/Verifier so I’m going to call them Pepe and Veronica1.

A signature refresher

Pepe has a secret key, sk, and a public key, pk. Let’s also assume that pk is a function of sk, say pk = F(sk) where F is hard to invert. He needs to prove to Veronica that he actually knows sk, without letting her know anything about sk. If this sounds suspiciously like a zero-knowledge proof, then give yourself a gold star.

There are a few desireable qualities:

  • small keys
  • small signatures
  • quick signing/verification

The basics of a signature protocol are generally fairly consistent, so let’s chat about Pepe and Veronica!

Pepe needs to prove that he knows sk such that pk = F(sk) (i.e. the public key is some hard function of a secret key). He could just send sk that over to Veronica, who would compute F(sk) to check, but that’s not very zero-knowledge.

Seems like it would be a good idea to add some randomness in. Pepe grabs a random number r out of his magic hat and tells Veronica c = F(r). Veronica isn’t quite sure about this whole thing, so she asks Pepe to tell her either the value of r or the value (sk + r)– this is the challenge.

  • Veronica requests r –> computes c1 = F(r) and verifies c1 = c
  • Veronica requests (sk + r) -> computes c1 = F(sk+r) and verifies c1 = c * F(sk)

I’ve glossed over some (a lot) of details, but let’s assume that’s how you combine c and pk to check equivalence 2.

Pause here. Have we leaked any information about sk? Nope. The challenge requests two totally random values (assuming the magic hat is working properly). Can we tell if Pepe actually knows sk? If he actually knows it, he can respond correctly to either challenge. Can Pepe cheat? Maybe.

If Pepe knows that Veronica will request r, then everything is unicorns and rainbows. He doesn’t even have to know sk in this case. If Pepe knows that she’ll ask for (sk + r), then he’ll pick a random value r’ and compute c’ = F(r’)/F(sk). Now he’s cheated and Veronica is sad with 0.5 probability. Cheating is only possible if Pepe anticipates the challenge:

  • If Pepe thinks Veronica will pick r, but she asks for (sk + r), he’ll fail. He doesn’t know sk.
  • If Pepe thinks Veronica will pick (sk + r), but she asks for r, he would have to invert the hard problem F if he cheated as described.

Ok, so if Pepe and Veronica only run this protocol once, then he can cheat half the time. So, let’s just do it over and over until that probability becomes acceptably negligible.

Identification versus signature

The above can easily be made non-interactive using hashes, but I’m going to just state that and leave it.

There’s a slight nuance between identification and signing. The interactive protocol above is an identification protocol, so a non-interactive version directly translates to a digital signature. But beyond that, a digital signature implies both identity/authentication and message integrity, while identification gives no guarantees about the latter.

Also, not all interactive protocols are identification protocols. For a non-trivial identification protocol, you need a public key that corresponds in some (difficult to invert) way to a private key.

Hand-waving over, lets talk Picnic

Picnic is the proposed PQ signature scheme. It requires a hash function and a block cipher–yay I don’t have to learn a new math in order to figure this one out (I hope). And–this is where it gets real–Picnic doesn’t use a Merkle tree! Nothing against them, but she makes a great point that there’s some benefit to a diversity of approaches.

Spoilers: Picnic achieves small keys, large signatures, moderate signing and verification time. They suggest SHAKE34 and LowMC as the hash function and block cipher.

ZKBoo

In addition to the hash function and block cipher, we need some way to write the proofs required by the scheme. Enter ZKBoo, a ZK proof system for boolean circuits.

  • secret key corresponds to inputs x1…xn
  • public key corresponds to outputs y1…ym5
  • the boolean circuit is the hard-to-invert function

Picnic Interactive Protocol

Great, now you’re a PQ expert!

Is it ZK? a1, b1 don’t leak anything about a or b. c1, c2 don’t reveal anything abut a or b either. Looks good to me. Thanks magic hat of randomness!

Just like current signature schemes, the cheating probability is 0.5, so you have to run multiple rounds with fresh random numbers to reduce this.

There are two ways they’ve transformed the interactive protocol into a non-interactive signature scheme:

  1. Fish Signatures: uses the FS transform
  2. Picnic Signatures: uses Unruh’s transform

On the way to proposing these two signatures, they optimized ZKBoo to form ZKB++, resulting in smaller signature sizes. They’ve proven each secure in their respective random oracle models, and they’ve written a reference implementation. Using this implementation, they’ve done some initial TLS experiments that look promising (1.4-1.7x performance hit).

Certificate Transparency

My only note from this talk reads

In summary, CAs are a bargain with the devil


1: I’m aware that Peggy/Victor occurs in the literature, but I like my version more.

2 I’m basically leaving out all of the discrete log details. In this case, the challenge would be (sk + r) mod (p - 1), where pk = g^sk mod p. It’s then just some arithmetic to see that g^(x+r) mod (p-1) = c * pk mod p, where c = g^r mod p as long as I typed that up correctly without LaTeX.

3: Protip - if using a monitored computer, maybe wait til you get home before typing ‘shake hash’ into Google

4: Also, technically SHAKE is an extendable-output function (XOF), but you can use them in similar ways to hash functions

5: Yes, I’m morally opposed to 1-indexing, but that’s how they did it

Last week I went to Real World Crypto (RWC aka my personal favorite IACR conference) and the High Assurance Crypto Symposium (HACS).

RWC - Real World Crypto

RWC is a unique opportunity that brings theorists and implementors together. It ends up featuring a diverse set of talks that span from post quantum signature schemes to zero knowledge proofs in cryptocurrency. All of the talks are posted to the youtube channel

There were a lot of excellent talks, so I’ll try to write about a selection of my favorites. Surprisingly, I’ll start with one about ZCash.

Zero-Knowledge Proofs

ZK proofs are a way for one party to prove that they know something without having to disclose it. For example, Alice wants to buy a sudoku solution from Bob, but doesn’t want to pay until she knows that his solution works. Bob doesn’t want to give Alice the solution until she pays. Instead of gridlocking, Bob wants to prove to Alice that his solution will work. Then she’ll pay him and she’ll solve her puzzle.

The problem with most cryptocurrencies is that everything about the blockchain is public–you’re exposing every transaction you make.

Schnorr identification

One practical application of this is Schnorr identification/signatures. Alice wants to prove that she knows the secret key a, but she doesn’t want to leak her secret key in the process. You can see a full description here. It relies on an interactive protocol. By using hash functions, you can make this non-interactive.

ZCash

ZCash is a privacy-preserving cryptocurrency. It uses zkSNARKs to non-interactively prove that a valid transaction has occurred without revealing any knowledge about addresses or values. In order to do this, it requires secure parameters.

Yes. There’s a ceremony. And it was apparently crazy. It was a 6 person multi-party computation (MPC), and they drove around rural canada while doing the computations to make sure no one was following them. It’s the perfect combination of ridiculous (you have to pick people before hand, plus the aforementioned ceremony) and cool (it’s secure even if 5/6 parties are dishonest). However, it’s not scalable or sustainable. So, they’ve come up with a new MPC, Powers of Tau.

Ok, now we’ve done our ceremony to the ZK gods, and we’re off to prove some things! One important thing to note: ZK requires that we can’t tell the difference between parameters generated honestly and backdoored parameters. That said, let’s consider ZK contingent payments (aka Alice, Bob and the great sudoku solution). The buyer has to generate the parameters, which protects them from a dishonest seller. However, the seller is vulnerable to a malicious buyer.

Subversion-resistance

This scenario is called subversion, and it’s a problem. If the trusted setup is subverted, then an adversary can create false proofs…which means they can mint money! Luckily, it doesn’t break anonymity, but it will break everything else when someone makes a bunch of fake ZCash.

Luckily, subversion-resistance ZK SNARKs are here to rescue us! Maybe I’ll write about it after I write about all of the other cool things at RWC.

This was my first year attending HACS…and I think it’s the hardest my brain has ever worked. A lot of the work discussed there is in progress, so I won’t go into details. It’s amazing to see a group of brilliant people all directing their brainpower towards securing crypto instead of breaking.

In addition to all of the current research I learned about, I was able to have one-to-one discussions about topics I’ve never really understood (cough elliptic curves and lattice crypto cough) with experts. I won’t claim to understand them, but I’m less baffled by them at least.

It was an incredible experience, and to explain why, let’s back up a century.

Crypto has been in a consistent cycle since its inception: people write algorithms then people break them. In the early 20th century, everything changed. A new cipher method arrived, called the one-time pad or Vernam’s cipher.

One-time pad

Previous ciphers were variations on substitution ciphers–instead of sending your message directly, you swap out each character for a different one. However, this leaves patterns in the ciphertext. By looking at the frequency of the enciphered characters, a cryptanalyst will be able to recover the plaintext and key. This is, of course, the simplest form, but even with additional complications, substitution ciphers tend to leave patterns in the ciphertext that can be exploited.

What’s missing? Randomness. Humans are really terrible at randomness. The one-time pad introduced two critical notions in cryptography.

First instead of swapping one character for another, you can combine them mathematically. Let each alphabet letter be represented by its position in the alphabet, and then instead of substituting it, use modular arithmetic to combine it with the key.

What happens if the key is shorter than the message? If the key is too short, then you will have to loop it in order to encrypt the entire message. This is a problem, because by repeating the key, you introduce a pattern that can be exploited.

There are three consequences from this:

  1. The key must be at least as long as the message
  2. The key cannot be reused
  3. The key must be random

If these conditions are met, then it’s mathematically proven that the one-time pad encryption scheme is “perfectly secure”–the ciphertext gives no additional information about the plaintext. As long as the key is random, all possible plaintexts are equally likely.

It seems like this would solve cryptography, but I’m writing about the Next Big Thing (TM), so this is clearly not the case. While the one-time pad is perfectly secure, it’s hard to use properly, and there are severe consequences to misuse. In order to use a one-time pad, you have to somehow exchange a lot of perfectly random, possibly very long, keys in advance. Obviously, there’s a scalability issue there as well. Then, if you make a mistake and reuse a key, this is what happens (in the very loosest mathematical sense):

Suppose we have two plaintexts, p1 and p2 of length n, and a key k of length n. Using k, we encrypt both p1 and p2, resulting in ciphertexts c1 and c2. The one-time pad scheme often uses XOR to combine the key and plaintext, so if we XOR the two ciphertexts together, the key will cancel out. This reveals the value (p1 XOR p2), which violates the property of perfect secrecy. Additionally, if a cryptanalyst can guess part of the plaintext (e.g. all messages starting with ‘hello’), then they can recover part of the key.

Despite these shortcomings, the one-time pad represents a turning point in cryptography. For the first time, cryptographers are mathematically verifying properties of an encryption scheme.

What does this have to do with formal verification?

Formal verification

For the purposes of this discussion, there are two main components of crypto software: primitive and protocol. Both of these are described by specifications to try and enforce that all implementations behave the same (and proper) way. Protocols like TLS are much more complicated than primitives, so that’s what I’ll focus on.

Crypto primitives are the building blocks for protocols and applications. They include block ciphers, public key ciphers, elliptic curves and much more. The specifications are long (20+ pages) of diagrams and textual descriptions of what an algorithm is supposed to do. Often, they include reference implementations to assist developers.

In the past, researchers and developers have used a combination of manual code inspection, fuzzing and testing to detect and fix bugs one by one. Wouldn’t it be better to be able to mathematically prove that an algorithm or implementation is secure against entire categories of vulnerabilities?

Just like Claude Shannon mathematically proved that the one-time pad is perfectly secure given certain constraints, formal methods allow us to prove attributes about algorithms and implementations. Some examples of what can be formally proven:

  • constant time/secret independence
  • functional correctness
  • memory safety
  • program equivalence

Suppose I want to implement SHA-256. After completing my implementation, I’d like to prove that it conforms to the published specification (i.e. functional correctness). This requires a formal definition of the specification and a way to map the implementation to the specification. There are various tools and techniques such as Coq and F*, usually using an underlying SMT solver.

You can think of an SMT (satisfiability modulo theories) solver as a magic box that takes in a set of constraints (preconditions, postconditions, loop conditions, assertions) and decides if the properties hold. If this isn’t a great explanation, it’s probably because I’m still trying to wrap my head around it.

In the end, I would (hypothetically) have an implementation of SHA-256 that I’ve mathematically proven conforms to the published specification.

Why do I think that this is such a big deal?

When I first had to write a proof, part of me wondered what the point was. Consider the pythagorean theorem. It’s obvious that it’s true for (3,4,5) and (5,12,13), so let’s just go with it, right? Apparently that argument ‘lacks rigor.’ Instead, you have to actually prove it that for all possible values of a and b, there exists a c such that the theorem holds. The upside is, once it’s been proven, you don’t have to worry about it breaking!

Being able to formally state and prove properties of crypto algorithms and implementations for all possible inputs has enormous potential to secure the heart of trusted computing. Instead of finding and fixing bug by bug, we could be able to definitively say that bug categories will not happen. And that’s insanely exciting.

Tools/Projects/Resources

A non exhaustive list of things I learned about at HACS:

  • ctverif - constant time verification
  • HACL*: verified crypto primitives in Firefox
  • Verifying curve 25519: optimized assembly, HACL*
  • Tamarin: Security protocol verification tool
  • Coq: Proof assistant
  • F*: functional programming language intended for program verification
  • Project Everest: working towards building a fully verified HTTPS stack
  • Cryptol: specification language intended for formally documenting crypto algorithms

A huge thank you to everyone who attended HACS, and especially the organizers. I’m grateful for the experience and looking forward to learning a lot more.

Update

As mentioned in the original post, it’s been a while since I attempted any stack smashing, and I did something horribly wrong!

up/down/left/right are hard

Here’s some more apples-to-apples Rust/C:

fn main() {
    let local = "hello, world";
}

rust stack

The pointer to the string is circled in red, and the return address is in blue. This indicates that even a non-mutable &str is allocated on the heap, making a buffer overflow a less viable attack.

int main ( int argc, char **argv ) {
     char buf[100];
     strcpy(buf, "hello, world\0");
     return 0; 
}

c stack

The “hello, world” string is circled in red, and the return address is in blue. You can see that if an attacker continued to write past the bounds of the string, it would be easy to overwrite the return address.

So, Rust pushes things to the stack the same way that C does (which is actually a relief to me, because I was really confused about how/why/what was happening). However, even an unmodifiable &str is still allocated on the heap, making stack smashing significantly more difficult.

Motivation

I’ve recently been looking into the usage of unsafe code in Rust programs (unsafe unicorn). I was curious about what happens when you use a C-style for loop in Rust.

Considering the following two code snippets:

let x = vec!(1,2,3);
for i in x {
	println!("{}", i);
}
/// outputs:
/// 1
/// 2
/// 3
let x = vec!(1,2,3);
for i in 0..4 {
	println!("{}", x[i]);
}
/// outputs
/// 1
/// 2
/// 3
/// thread 'main' panicked at 'index out of bounds: the len is 3 but the index is 3', ...

It turns out that in the implementation of slice, bounds checking is on by default. The function slice_index_len_fail can be called from index and index_mut. In order to avoid this, there would have to be a custom implementation of SliceIndex<T>, and I can’t think of a decent reason why this would happen (if you can, let me know).

After a while, I decided that safe Rust would (rightly) prevent ‘traditional’ overflows, even in non-idiomatic Rust. Therefore, I was going to have to do terrible things and abuse unsafe.

I don’t look at assembly a ton–let me know if I’ve done something horribly, horribly wrong here.

Some of this post is general playing around to see what Rust looks like in gdb, and some of this is actually attempting a contrived (stack) buffer overflow.

Buffer Overflows

This post assumes some familiarity with buffer overflows and assembly. If you don’t know what these are, I recommend:

Or just look at xkcd

Using GDB with Rust

I use a Mac, but I prefer gdb to lldb, so I followed the instructions here. I still had to run with sudo, and I’m pretty sure that’s because of the way I codesigned gdb.

I used rust-gdb, which enables pretty-printing. Rustup installs it by default, so you should be good to go. When running it, point rust-gdb at the binary in target/debug/deps/<crate>-xxx–if you use the binary in target/debug/<crate>, gdb won’t be able to load symbols. It will still work, but you won’t be able to run commands like info locals or p x. You also won’t be able to step through lines of code, although next instruction does work.

All of the assembly I’ll be referencing is in x86 AT&T syntax (instr src dest).

Setting breakpoints

Set breakpoints just how you normally would:

  • b do_bad_things
  • b main
  • rbreak src/main.rs:.: breaks on all functions in main
    • for some reason, this would only work for me after I manually broke on a function in main.rs

Resources

Diving In

#[no_mangle]
pub fn chain() {
    let x = 3;
    let y = 4;
    let z = x + y;
    chain1()
}

#[no_mangle]
pub fn chain1() {
    chain2()
}

#[no_mangle]
pub fn chain2() {
    let x = 3;
    let y = 4;
    let z = x + y;
    chain3()
}

#[no_mangle]
pub fn chain3() {
    chain4()
}

#[no_mangle]
pub fn chain4() {
    // put some temp vars on the stack
    let x = 3;
    let y = 4;
    let z = x + y;
    println!("{}", z);
}

pub fn main() {
	chain();
}

I wrote a very simple program to look at how Rust allocates memory with the stack. I chained 5 functions together and called the first from main. In gdb, I set breakpoints on each function so I could look at the call stack, then within some functions, I created local variables.

main

First, gdb breaks at main.

 (gdb) info frame
Stack level 0, frame at 0x7fff5fbffa80:
 rip = 0x1000032b2 in for_test::main (src/main.rs:65); saved rip = 0x100030ead
 source language rust.
 Arglist at 0x7fff5fbffa70, args: 
 Locals at 0x7fff5fbffa70, Previous frame's sp is 0x7fff5fbffa80
 Saved registers:
  rbp at 0x7fff5fbffa70, rip at 0x7fff5fbffa78

(gdb) x 0x100030ead
0x100030ead <panic_unwind::__rust_maybe_catch_panic+29>:	0x8348d889

The top of the frame is at 0x7fff5fbffa80, the bottom is at 0x7fff5fbffa70 and the return instruction pointer is at 0x7fff5fbffa78. If we look at this address, we see 0x7fff5fbffa78: 0x00030ead 0x00000001. What’s happening here is that the main function returns to maybe_catch_panic. You can also see this address in the “saved rip” spot. Another thing to notice is that there’s (yet another) rip = 0x1000032b2. This is the address for the main function, so a function called from main will have this set as their saved rip.

The first thing that I noticed is how small the stack for each function is–it’s only 2 addresses:

address  
0x7fff5fbffa80 top of frame
0x7fff5fbffa78 rip
0x7fff5fbffa70 rbp/arglist/locals.

Let’s compare this to a stack setup in C:

void bar(char * p) {
	char buf[100];
	strcpy(buf, p);
}

When you call a function in C, the argument is pushed to the stack. Then, when you allocate buf, it’s allocated locally (i.e. on the stack, not the heap). This pushes the stack pointer down 100 bytes (stack grows down). This means that the end of the 100 byte buffer immediately precedes the stack pointer, which in turn immediately precedes the return instruction pointer.

  lower memory addresses
 
100 byte buffer  
rsp  
rip  
p  

At this point, it should be clear that a Rust stack looks very different than a C stack. The C stack has to fit all of the local variables. Moreover, those local variables, including things like strings, are allocated right before the return instruction pointer, so if you can overwrite the buffer, you can set that return pointer to anything you’d like (say, some arbitrary code you wrote earlier in the buffer?).

Local variables

If Rust doesn’t put the local variables on the stack like C, where does it put them?

To answer this, we’ll look at the chain* functions. For brevity, I’ll only be using the last 2 bytes of the addresses (prefix 0x7fff6fb)

function address register  
main 0xfa80 top of frame  
    0xfa78 rip
    0xfa70 rbp
chain 0xf9c0 top of frame  
    0xf9b8 rip
    0xf9b0 rbp
chain1 0xf9b0 top of frame  
    0xf9a8 rip
    0xf9a0 rbp
chain2 0xf9a0 top of frame  
    0xf998 rip
    0xf990 rbp
chain3 0xf990 top of frame  
    0xf988 rip
    0xf980 rbp
chain4 0xf980 top of frame  
    0xf978 rip
    0xf970 rbp

The functions chain, chain2, and chain4 each instantiate the same local variables x, y, z:

function var address  
chain x 0xf9a4  
    y 0xf9a8
    z 0xf9ac
chain2 x 0xf974  
    y 0xf978
    z 0xf97c
chain4 x 0xf8e4  
    y 0xf8e8
    z 0xf8ec

This looks the same. It’s like, why did I even bother with this post?

   0x0000000100003148 <+8>:	movl   $0x3,-0xc(%rbp)
   0x000000010000314f <+15>:	movl   $0x4,-0x8(%rbp)
   0x0000000100003156 <+22>:	mov    -0xc(%rbp),%eax
   0x0000000100003159 <+25>:	add    -0x8(%rbp),%eax

Local strings

Now, let’s consider

#[no_mangle]
pub fn local_buf() {
    let mut buf = String::with_capacity(100);
    buf.push('h');
    buf.push_str("ello");
    let buf1 = "h";
    let buf2 = "meow";
}

The frame looks like this:

   
0xf9b0 top of frame
0xf9a8 rip
0xf9a0 rbp/args/locals
 
0xf980 buf2
0xf970 buf1
0xf958 buf
(gdb) p &buf
$5 = (alloc::string::String *) 0x7fff5fbff958
(gdb) p buf
$6 = alloc::string::String {vec: alloc::vec::Vec<u8> {buf: alloc::raw_vec::RawVec<u8, alloc::heap::Heap> {ptr: core::ptr::Unique
    <u8> {pointer: core::nonzero::NonZero<*const u8> (0x100624000 "hello\000"), _marker: core::marker::PhantomData<u8>}, cap: 
        100, a: alloc::heap::Heap}, len: 5}}
(gdb) p &buf.vec.buf
$7 = (alloc::raw_vec::RawVec<u8, alloc::heap::Heap> *) 0x7fff5fbff958
(gdb) x/8x &buf.vec.buf
0x7fff5fbff958:	0x00624000	0x00000001	0x00000064	0x00000000
0x7fff5fbff968:	0x00000005	0x00000000	0x0003c310	0x00000001
(gdb) x 0x100624000
0x100624000:	0x00000068

That’s…a little complicated. Let’s break it down:

  • 0x7fff5fbff958: address of buf, which stores 0x100624000
  • 0x100624000: the pointer to the actual data

There’s something important happening here: We aren’t necessarily pushing the actual variable to that spot–we might be pushing a pointer to a variable elsewhere in memory

  • Above, in the chain example, the ints were pushed directly to the stack below
  • Here, we have both &str and String represented by pointers to the actual data

In Rust, a variable that can “grow” during execution (i.e. strings, vecs) is allocated on the heap, because it can’t be known how big it is at compile time.

(gdb) info locals
buf2 = &str {data_ptr: 0x10003c311 <str.c> "meowhello, world!\000", length: 4}
buf1 = &str {data_ptr: 0x10003c310 <str.b> "hmeowhello, world!\000", length: 1}
buf = alloc::string::String {vec: alloc::vec::Vec<u8> {buf: alloc::raw_vec::RawVec<u8, alloc::heap::Heap> {ptr: 
    core::ptr::Unique<u8> {pointer: core::nonzero::NonZero<*const u8> (0x100624000 "hello\000"), _marker: 
        core::marker::PhantomData<u8>}, cap: 100, a: alloc::heap::Heap}, len: 5}}

When we look at all of this data together, there’s another really interesting thing happening. Earlier, in the main function, I create a &str s = "hello, world", which is located at 0x10003c315. When I create buf1 and buf2, they are pushed to the memory directly before s, while the String buf is allocated to a different area of memory. Although these variables are initialized in the order s, buf1, buf2, notice that they are laid out at buf1, buf2, s instead of buf2, buf1, s as you might expect. This is (maybe) because all of the local variables for a frame are allocated (uninitialized) upon frame-entry. They are then initialized by statements within the functions, and the compiler enforces that they can’t be used until they’ve been initialized.

Buffer Overflow

#[no_mangle]
pub fn abuse_vec(v: &mut Vec<i32>) {
    unsafe {
        v.set_len(15);
    }

    overflow(&v);
}

#[no_mangle]
pub fn overflow(v: &Vec<i32>) {
    for x in v.iter() {
        println!("{:?}", x);
    }
}

#[no_mangle]
pub fn do_bad_things(s: &str) {
    unsafe {
        let bad = s.get_unchecked(0..20);
        println!("{:?}", bad);
    }
}

fn main() {
    let mut v = vec![1];
    let mut s = "hello, world!"; // 68 65 6c 6c 6f 2c 20 77 6f 72 6c 64

    do_bad_things(&s);

    println!("{:?}", s);

    abuse_vec(&mut v);

    overflow(&v);

}

I don’t have ASLR turned on, so everything is in the same places in memory between builds. First, consider attempting to abuse v to overwrite the return instruction pointer–v is located at 0x100616008 and we would need to overwrite the memory at either 0x7fff5fbff9b8 (location of return instruction pointer) or 0x10000710b (location of the function we’re returning to–not precisely a stack buffer overflow, but oh well) in order to take control of the program’s execution.

(gdb) info frame
Stack level 0, frame at 0x7fff5fbff9c0:
 rip = 0x100006ad4 in for_test::abuse_vec (src/main.rs:10); saved rip = 0x10000710b
 called by frame at 0x7fff5fbffa80
 source language rust.
 Arglist at 0x7fff5fbff9b0, args: v=0x7fff5fbff9d8
 Locals at 0x7fff5fbff9b0, Previous frame's sp is 0x7fff5fbff9c0
 Saved registers:
  rbp at 0x7fff5fbff9b0, rip at 0x7fff5fbff9b8
(gdb) p v
$4 = (alloc::vec::Vec<i32> *) 0x7fff5fbff9d8
(gdb) p &v
$5 = (alloc::vec::Vec<i32> **) 0x7fff5fbff9a8
(gdb) x/2x 0x7fff5fbff9d8
0x7fff5fbff9d8:	0x00616008	0x00000001
(gdb) x 0x100616008
0x100616008:	0x00000001

This means that the question is: can a buffer at 0x100616008 overwrite memory at 0x7fff5fbff9b8? The stack grows down, so objects pushed to the stack later have lower memory addresses. 0x100616008 is a (much) lower memory address than 0x7fff5fbff9b8. In theory, we could overwrite this, but that is a lot of memory (if my calculator is right: 17591312306998 bytes) to write, and the chances of it working don’t seem high to me.

I did try to set the length of the vector to something absurd to see what would happen:

#[no_mangle]
pub fn abuse_vec(v: &mut Vec<i32>) {
    unsafe {
        v.set_len(794079);
    }

    v[794077] = 0x00006ae4;
    v[794077] = 0x00000001;
    overflow(&v);
}
(gdb) info frame
Stack level 0, frame at 0x7fff5fbff950:
 rip = 0x1000068b3 in for_test::abuse_vec (src/main.rs:5); saved rip = 0x100006e15
 called by frame at 0x7fff5fbffa80
 source language rust.
 Arglist at 0x7fff5fbff940, args: v=0x7fff5fbff978
 Locals at 0x7fff5fbff940, Previous frame's sp is 0x7fff5fbff950
 Saved registers:
  rbp at 0x7fff5fbff940, rip at 0x7fff5fbff948
(gdb) x/2x 0x7fff5fbff948
0x7fff5fbff948:	0x00006e15	0x00000001
(gdb) n
7	        v.set_len(794079);
(gdb) 
10	    v[794077] = 0x00006ae4;
(gdb) 

Thread 2 received signal SIGSEGV, Segmentation fault.
0x00000001000068e3 in for_test::abuse_vec (v=0x7fff5fbff978) at src/main.rs:10
10	    v[794077] = 0x00006ae4;
(gdb) x/2x 0x7fff5fbff948
0x7fff5fbff948:	0x00006e15	0x00000001

S-s-s-s-s-s-s-segfault!!!!!

sorry, compiler

What about a buffer at 0x100616008 overwriting memory at 0x10000710b? The buffer is at a higher memory address, meaning that it would need to write backwards. Due to type safety, this would be difficult–indices need to be usize.

do_bad_things

I played around with a string, but I couldn’t quite manage to make get_unchecked_mut to compile. The variable s is located at 0x7fff5fbff890, but the data is at 0x10003c195, so this approach suffers from the same problems.

(gdb) p &s
$1 = (&str *) 0x7fff5fbff890
(gdb) p s
$2 = &str {data_ptr: 0x10003c195 <str.g> "hello, world!\000", length: 13}
(gdb) x/2x 0x7fff5fbff890
0x7fff5fbff890:	0x0003c195	0x00000001

Is a buffer overflow possible?

Not really.

Buffer overflows rely on the fact that the buffer is pushed to the stack before the return instruction pointer (and, of course, a missing bounds check). Rust sticks bounds checks all over the place, but even if you bypass those, either through abuse of unsafe or custom types that skip bounds checks, the stack memory layout makes it really difficult (if not impossible). A key protection is that Rust doesn’t ever (?) put a ‘growable’ object like a &str/String/Vec on the stack. This means that an exploit would need to overwrite very large amounts of data, likely causing a crash in other ways before taking control of the program.

This supports Rust’s memory safety claims, as well as providing a fun way to play with rust-gdb.

Further work

I think it would be really neat to look at how #[repr(C)] looks in memory. I also want to look at some crypto libraries to see how data is sanitized, etc. Overall, I think data leakage in Rust is likely a more reasonable exploit approach as opposed to modifying control.

I hope to try some other classic attacks on Rust to see what happens.

Other Resources

tl;dr;

Programming is hard. I made some really silly mistakes. Avoid globals, embrace code review and tests.

Motivation

When I was speaking with my grad school advisor a few weeks ago, we had the idea do some basic analysis on unsafe usage in Rust. It’s a fairly simple concept, so I quickly wrote up something to read a file line-by-line and count lines in unsafe functions or blocks.

Fun story time: Making sure that the script doesn’t think the unsafe block/function ends too early is a simplification of one of my favorite “easy” programming questions – verify that a statement with various delimiters is valid (e.g. that the open and close delimiters match). You can probably see that in my code since I love pushing delimiters to stacks (even when I don’t need to). Enough about my weird hobbies.

I was then distracted by a conference for a week, and when I returned to work yesterday, I finished my script off by writing something to interact with Github. The idea is that you could run this over all Rust projects in Github (or some subset–I just wrote it yesterday people!) and see how people are using unsafe.

Instead of discussing what we might be able to learn from the script’s correct results, this post is about the ways I messed it up and then posted the mistakes to twitter.

Mistake: abuse of global variables

Yup. I stored all of my counts in globals. Yes, I heard my Intro to Programming professor’s voice in my head saying “DON’T use globals unless you have to!!!”

I forgot to clear the counts between repositories.

I noticed this right as I published a tweet about my work. “Why are these numbers monotonically increasing,” I thought. Then I screeched and immediately deleted it.

Globals abuse

Mistake: abuse of endless if/if/elif/else/more ifs

Ok, so that was a pretty gigantic mistake, right? Every real developer knows to avoid globals and if you don’t, make sure you reset them. Oops. But at least I fixed it before I told The Whole World (who reads Rust-related tweets) about this. That’s great–so I tweeted. I even mentioned my near miss!

As it turns out, I had another glaring mistake. This morning, I started adding some stats on how many panic!s there are. As I read over my code, I thought, “something is wrong here…”

 for line in open(filename).readlines():
        # skip comment lines
        if re.match(regex, line):
            comment += 1
        # skip blank lines
        if len(line.strip()) == 0:
            blank += 1

        code += 1
        #...

In case you missed it (like I did), I say I’m skipping comments/blank lines and then I don’t! It’s an easy fix, but why did I decide to make such an awful cascade of ifs? No clue. Seemed like a good idea at the time.

Endless if

Mistake ?

So this is where I’m currently at. It doesn’t 100% match up with the comparable cloc stats, but it’s a lot closer.

More mistakes?

Lessons

Don’t be like me.

Listen to your professors

Avoid globals. Please don’t take my degree away.

Make your code easier to read

If it’s easier to read, it’s easier to catch silly mistakes (this is why I avoid Perl).

Code reviews are the best

Someone else definitely would have caught this in a review (I hope)

Testing is also the best

If I’d initially compared my results to cloc output, I probably would have caught these mistakes earlier and not told all of Twitter.

Conclusions

The errors I detail here are logic errors–I, the programmer, did something horribly wrong. This is a huge problem in security implementations. I work on practical security and implementations…so…buries face in formal verification papers

Rust wouldn’t have saved me from these particular mistakes, but it has saved me from tons of other mistakes, like typos that would result in similar logic errors.

I’ve been programming for 8 years. I’ve had one job or another (that pays me to program!) for 5 of those years. In college, I helped teach intro to programming (do as I say, not as I do, please). I still make really silly mistakes.

Some developers will tell you that real devs don’t make mistakes like this. If that’s the case, then I guess I’m not a real dev (and I’m fine with that). I think it’s probably more likely that they’re lying or they don’t do much work.

Certificate verification

Servo’s security infrastructure is heavily dependent on OpenSSL. I created an experiment to compare certificate verification using WebPKI and OpenSSL. I found it convenient to interact with WebPKI via Rustls.

This is part of an effort to update hyper and rust-openssl in Servo. It’s important to note that I’m not changing all of the code away from OpenSSL, just the certificate verification. OpenSSL still manages the connection, which results in some conversion overhead to the appropriate types for rustls/webpki.

In order to change the verification function, you have to modify set_verify_callback to point to the desired function when you’re creating the SSL object. Then I wrapped different parts of the verification algorithms with timing data:

Timing Measures

OpenSSL:

  • roots-creation: (subset of http-connector-creation) this is a rustls artifact that I forgot to delete for my openssl test
  • verify-hostname: time spent verifying that a certificate is valid for a domain
  • http-connector-creation: total time creating the connector object
  • matches-wildcard
  • matches-dns:
  • openssl-verif-call: measures the total time spent in the openssl verification function
  • connection: measures how long it actually takes to connect (i.e. run ssl.connect)
  • total-openssl-verify

Rustls:

  • rustls-verify: measures the total time spent in the rustls verification function (either parallel_verify_server_cert or verify_server_cert)
  • chain-creation: measures how long it takes to convert the openssl x509 chain to the rustls certificate chain
  • roots-creation: (subset of http-connector-creation) time required to create the rustls root certificate store
  • http-connector-creation: total time creating the connector object
  • connection: measures how long it actually takes to connect (i.e. run ssl.connect)
  • total-rustls-verify time: measures total time performing all steps required for rustls verification

All values are averaged over the number of times a method was called while opening a site.

There are two versions of Rustls that I tested on–one does all verification steps in serial, while the other does them all in parallel. Parallel rustls still has room for improvement– for more information, see webpki.

Sites

The sites I picked for testing were the 8 featured on servo’s front page, plus a few I frequently use. Most of them use TLS ECDHE RSA with AES 128 GCM SHA256 and 128 bit keys, except those noted below

Results

I’m not sure what happened with hackernews-rustlsserial, and I’ll try to get new numbers for it.

I compared results for total connection time and total verification time. For total connection time, openssl was fastest for 5/12 (excluding hackernews) sites, rustlsserial was fastest for 4, and rustlsparallel for the remaining 3. For overall verification time, openssl was fastest for 11 sites, and rustlsparallel was fastest on washingtonpost.com.

It’s interesting that openssl was almost uniformly quicker at just performing verification, but not for establishing a connection. I’m not sure why this would be. If anyone has ideas, let me know :)

Times are shown in ms.

site method roots creation http connector creation openssl/rustls verify call total connection time total verification time
arstechnica openssl 6.5937645 3.06476595 0.04212679 7.63642713 0.11863110
arstechnica rustlsparallel 0.6452306 1.8578739 0.9613585 10.6051663 0.9679321
arstechnica rustlsserial 1.7092342 4.8119877 0.8465297 17.3814024 0.8523814
cnn openssl 0.5902370 3.33709690 0.00156567 5.87286853 0.00410566
cnn rustlsparallel 0.4306289 2.5159100 0.3190672 9.7441715 0.3259468
cnn rustlsserial 0.5596800 2.3019310 0.2837703 6.2241893 0.2915407
duckduckgo openssl 0.5305152 2.91319830 0.00221078 7.69686665 0.00550160
duckduckgo rustlsparallel 0.4963679 3.2570464 0.4329721 6.4144129 0.4383328
duckduckgo rustlsserial 0.5634392 2.5714297 2.1426261 5.4416704 0.2206577
github openssl 0.5259603 2.41714400 0.00726623 10.90148742 0.01794724
github rustlsparallel 0.4670057 2.2619585 5.4297168 14.1635926 5.4348146
github rustlsserial 0.4736196 2.9527882 0.5425635 20.3668883 0.5584827
google openssl 0.4657012 3.11720415 0.00158668 5.99938325 0.00500675
google rustlsparallel 0.4081303 2.2226142 0.2490465 4.9481365 0.2554819
google rustlsserial 0.7276384 2.8976474 0.2454053 4.8469683 0.2522257
hackernews openssl 0.5978065 2.74829625 0.00170511 4.20313573 0.00576318
hackernews rustlsparallel 0.4728535 2.7132263 0.6241498 4.1972928 0.6394845
hackernews rustlsserial 2.3374316 0.4007136      
reddit openssl 0.3964899 2.13715120 0.08706821 7.40169574 0.21397945
reddit rustlsparallel 0.5623264 2.4189925 1.9196810 7.1750911 1.9263490
reddit rustlsserial 0.5554853 2.4069789 0.3140017 5.6085587 0.3186888
rust openssl 0.4763279 2.50936690 0.00071792 5.00488759 0.00246496
rust rustlsparallel 0.5137190 2.8609235 0.8248997 6.2613387 i0.8308361
rust rustlsserial 0.7270381 2.8080940 0.7364159 5.9658525 0.7529244
servo openssl 0.4126936 2.46113245 0.01265213 3.54343740 0.04969500
servo rustlsparallel 0.3729247 2.2147630 0.4230856 4.2786723 0.4297226
servo rustlsserial 0.4271293 2.6142965 0.5498572 5.1212375 0.5624017
stack overflow openssl 0.4872833 2.54147045 0.00214393 6.69359618 0.00602048
stackoverflow rustlsparallel 0.6955762 2.4821835 0.3383331 4.6982153 0.3459493
stackoverflow rustlsserial 0.6805226 2.6676572 0.3023453 5.4262767 0.3090781
twitter openssl 0.5633570 3.06855305 0.00996953 25.13172682 0.02554954
twitter rustlsparallel 0.4326043 2.1039143 2.9250449 16.1298042 2.9300035
twitter rustlsserial 0.5732324 2.8023081 4.0729707 14.1060498 4.0807530
wapo openssl 5.2944900 2.82199855 0.18614084 8.39432315 0.63647240
wapo rustlsparallel 0.3269752 2.2430216 0.5247874 6.2113378 0.5317807
wapo rustlsserial 0.5703944 3.0341653 0.5972499 7.0022414 0.6031256
wikipedia openssl 0.5330987 2.39788525 0.00302343 5.13799420 0.00806534
wikipedia rustlsparallel 0.4611093 2.5344541 0.4680453 4.9266177 0.4759743
wikipedia rustlsserial 0.4883241 1.9458110 0.4012761 4.9726309 0.4095681

Next steps

  1. webpki benchmarks ECDSA RSA
  2. parallel signature verification webpki
  3. Improve test set and method (this started out as an adhoc measurement, but now seems like it could yield useful data as development continues)

Cipherscan

10 Oct 2016 | View comments

Web Compatibility and TLS

During a dev-servo discussion about the merits of various TLS libraries, the question of web compatibility came up–what cryptographic protocols does Servo need to support in order to serve most of the web?

I decided to run cipherscan and get some updated results.

Results

You can see the full results here, but I’ll highlight what I consider the most interesting in this case.

Ciphers

Supported Ciphers Count Percent
3DES 472578 87.0229
3DES Only 491 0.0904
3DES Preferred 1450 0.267
3DES forced in TLS1.1+ 854 0.1573
AES 539545 99.3546
AES Only 49098 9.0412
AES-CBC 539101 99.2728
AES-CBC Only 4403 0.8108
AES-GCM 458011 84.3405
AES-GCM Only 405 0.0746
CAMELLIA 245146 45.1424
CHACHA20 68015 12.5246
CHACHA20 Only 1 0.0002
Insecure 42351 7.7987
RC4 131983 24.304
RC4 Only 111 0.0204
RC4 Preferred 11067 2.0379
RC4 forced in TLS1.1+ 6031 1.1106

Protocols

Supported Protocols Count Percent
SSL2 12822 2.3611
SSL2 Only 10 0.0018
SSL3 76905 14.1617
SSL3 Only 272 0.0501
SSL3 or TLS1 Only 46262 8.5189
SSL3 or lower Only 278 0.0512
TLS1 530593 97.7061
TLS1 Only 26478 4.8758
TLS1 or lower Only 58211 10.7193
TLS1.1 476556 87.7555
TLS1.1 Only 40 0.0074
TLS1.1 or up Only 12044 2.2178
TLS1.2 483237 88.9857
TLS1.2 Only 3365 0.6196
TLS1.2, 1.0 but not 1.1 4564 0.8404
Supported Handshakes Count Percent
ADH 781 0.1438
AECDH 8790 1.6186
DHE 302890 55.7757
ECDHE 476401 87.7269
ECDHE and DHE 263183 48.4639
RSA 472454 87.0001

Certificates

Certificate sig alg Count Percent
None 9328 1.7177
ecdsa-with-SHA256 47343 8.718
sha1WithRSAEncryption 14180 2.6112
sha256WithRSAEncryption 495204 91.1894
sha384WithRSAEncryption 7 0.0013
sha512WithRSAEncryption 62 0.0114
OCSP stapling Count Percent
Supported 132214 24.3466
Unsupported 410836 75.6534

Discussion

I initially compiled these stats because the Servo community brought up the possibility of using rustls (hyper crate) in Servo. Currently, rustls only supports TLS1.2, so it seemed like a good time to get some updated cipherscan results. Over 10% of the sites surveyed only supported TLS1.1 or lower. In a production browser, this would be way too high.

Mostly, I think these numbers can be useful for prioritization right now.