libmagic: The Blathering

By Evan Sultanik, Principal Security Engineer

A couple of years ago we released PolyFile: a utility to identify and map the semantic structure of files, including polyglots, chimeras, and schizophrenic files. It’s a bit like file, binwalk, and Kaitai Struct all rolled into one. PolyFile initially used the TRiD definition database for file identification. However, this database was both too slow and prone to misclassification, so we decided to switch to libmagic, the ubiquitous library behind the file command.

What follows is a compendium of the oddities that we uncovered while developing our pure Python cleanroom implementation of libmagic.

Magical Mysteries

The libmagic library is older than over half of the human population of Earth, yet it is still in active development and is in the 99.9th percentile of most frequently installed Ubuntu packages. The library’s ongoing development is not strictly limited to bug fixes and support for matching new file formats; the library frequently receives breaking changes that add new core features to its matching engine.

libmagic has a custom domain specific language (DSL) for specifying file format patterns. Run `man 5 magic` to read its documentation. The program compiles its DSL database of file format patterns into a single definition file that is typically installed to /usr/share/file/magic.mgc. libmagic is written in C and includes several manually written parsers to identify various file types that would otherwise be difficult to represent in its DSL (for example, JSON and CSV). Unsurprisingly, these parsers have led to a number of memory safety bugs and numerous CVEs.

PolyFile is written in Python. While libmagic does have both official and independent Python wrappers, we chose to create a cleanroom implementation. Aside from the native library’s security issues, there are several additional reasons why we decided to create something new:

  1. PolyFile is already written in pure Python, and we did not want to introduce a native dependency if we could avoid it.
  2. PolyFile is intended to detect polyglots and other funky file formats that libmagic would otherwise miss, so we would have had to extend libmagic anyway.
  3. PolyFile preserves lexical information like input byte offsets throughout its parsing, in order to map semantics back to the original file locations. There was no straightforward way to do this with libmagic.

The idea of reimplementing libmagic in a language with more memory safety than C is not novel. An effort to do so in Ruby, called Arcana, occurred concurrently with PolyFile’s implementation, but it is still incomplete. PolyFile, on the other hand, correctly parses libmagic’s entire pattern database and passes all but two of libmagic’s unit tests, and correctly identifies at least as many MIME types as libmagic on Ange Albertini’s 900+ file Corkami corpus.

The Magical DSL

In order to appreciate the eldritch horrors we unearthed when reimplementing libmagic, we need to offer a brief overview of its esoteric DSL. Each DSL file contains a series of tests—one per line—that match the file’s subregions. These tests can be as simple as matching against magic byte sequences, or as complex as seemingly Turing-complete expressions. (Proving Turing-completeness is left as an exercise to the reader.)

The file command executes the DSL tests to classify the input file. The tests are organized in the DSL as a tree-like hierarchy. First, each top-level test is executed. If a test passes, then its children are each tested, in order. Tests at any level can optionally print out a message or associate the input file with a MIME type classification.

Each line in the DSL file is a test, which includes an offset, type, expected value, and message, delimited by whitespace. For example:

10    lelong    0x00000100    this is a test

This line will do the following:

  1. Start at byte offset 10 in the input file
  2. Read a signed little-endian long (4 bytes)
  3. If those bytes equal 0x100, then print “this is a test”

Now let’s add a child test, and associate it with a MIME type:

10        lelong    0x00000100    this is a test
>20       ubyte 0xFF       test two
!:mime    application/x-foo

The “>” before the “20” offset in the second test means that it is a child of the previously defined test at the higher level.
This new version will do the following:

  1. If, and only if, the first test matches, then attempt the second test.
  2. If the byte at file offset 20 equals 0xFF, then print out “test two” and also associate the entire file with the MIME type application/x-foo.

Note that the message for a parent test will be printed even if its children do not match. A child test will only be executed if its parent is matched. Children can be arbitrarily nested with additional “>” prefixes:

10        lelong    0x00000100    this is a test
>20       ubyte     0xFF          test two
!:mime    application/x-foo
>>30      ubyte     0x01          this is a child of test 2
>20       ubyte     0x0F          this is a child of the first test that will be tested if the first test passes, regardless of whether the second child passes
!:mime    application/x-bar

If a test passes, then all of its children will be tested.

So far, all of the offsets in these examples have been absolute, but the libmagic DSL also allows relative offsets:

10      lelong    0x00000100    this is a test
>&20    lelong    0x00000200    this will test 20 bytes after its parent match offset, equivalent to absolute offset 10 + 20 = 30

as well as indirect offsets:

(20.s)      lelong    0x00000100    indirect offset!

The (20.s) here means: read a little-endian short at absolute byte offset 20 in the file and use that value as the offset to read the signed little-endian long (lelong) that will be tested. Indirect offsets can also include arithmetic modifiers:

(20.s+10)   read the offset from the little-endian short at absolute byte offset 20 and add 10
(0.L*0x20)   read the offset from the big-endian long at absolute byte offset zero and multiply by 0x20

Relative and indirect offsets can also be combined:

(&0x10.S)    read the offset from the big-endian short 0x10 bytes past the parent match
(&-4.l)      read the offset from the little-endian long four bytes before the parent
&(0.S-2)     read the first two bytes of the file, interpret them as a big-endian short, subtract two, and use that value as an offset relative to the parent match

Offsets are very complex!

Despite having existed for decades, the libmagic pattern DSL is still in active development.

Mischief, Unmanaged

In developing our independent implementation of libmagic—to the point where it can parse the file command’s entire collection of magic definitions and pass all of the official unit tests— we discovered many undocumented DSL features and apparent upstream bugs.

Poorly Documented Syntax

For example, the DSL patterns for matching MSDOS files contain a poorly documented use of parenthesis within indirect offsets:

(&0x10.l+(-4))

The semantics are ambiguous; this could mean, “Read the offset from the little-endian long 0x10 bytes past the parent match decremented by four,” or it could mean, “Read the offset from the little-endian long 0x10 bytes past the parent match and add the value read from the last four bytes in the file.” It turns out that it is the latter.

Undocumented Syntax

The elf pattern uses an undocumented ${x?true:false} ternary operator syntax. This syntax can also occur inside a !:mime directive!

Some specifications, like the CAD file format, use the undocumented regex /b modifier. It is unclear from the libmagic source code whether this modifier is simply ignored or if it has a purpose. PolyFile currently ignores it and allows regexes to be applied to both ASCII and binary data.

According to the documentation, the search keyword—which performs a literal string search from a given offset—is supposed to be followed by an integer search range. But this search range is apparently optional.

Some specifications, like BER, use “search/b64”, which is undocumented syntax. PolyFile treats this as equivalent to the compliant search/b/64.

The regex keyword has an undocumented T modifier. What is a T modifier? Judging from libmagic’s code, it appears to trim whitespace from the resulting match.

Bugs

The libmagic DSL has a type specifically for matching globally unique identifiers (GUIDs) that follows a standardized structure as defined by RFC 4122. One of the definitions in the DSL for Microsoft’s Advanced Systems Format (ASF) multimedia container does not conform to RFC 4122—it is two bytes short. Presumably libmagic silently ignores invalid GUIDs. We caught it because PolyFile validates all GUIDs against RFC 4122. This bug was present in libmagic from December of 2019 until we reported it to the libmagic maintainers in April 2022. In the meantime, PolyFile has a workaround for the bug and has always used the correct GUID.

Metagame

PolyFile is a safer alternative to libmagic that is nearly feature-compatible.

$ polyfile -I suss.png
image/png………………………………………………………..PNG image data
application/pdf…………………………………………………..Malformed PDF
application/zip…………………………………………………..ZIP end of central directory record Java JAR archive
application/java-archive…………………………………………..ZIP end of central directory record Java JAR archive
application/x-brainfuck……………………………………………Brainf*** Program

PolyFile even has an interactive debugger, modeled after gdb, to debug DSL patterns during matching. (See the -db option.) This is useful for DSL developers both for libmagic and PolyFile. But PolyFile can do so much more! For example, it can optionally output an interactive HTML hex viewer that maps out the structure of a file. It’s free and open source. You can install it right now by running pip3 install polyfile or clone its GitHub repository.

A Typical Day as a Trail of Bits Engineer-Consultant

Wherever you are in the world, a typical day as a Trail of Bits Engineer-Consultant means easing into your work.

Here’s a short video showing some of our European colleagues describing a typical day as a Trail of Bits Engineer-Consultant:

You generally set your own hours, to provide at least a couple of hours of overlap with colleagues around the world) by checking messages or comments received since you last checked in, and thinking about any requests for collaborative help. Then, depending on whether you’re on an audit or on non-client “bench-time”, your day could mean diving into code, or working on internal research and development, continuing education, or personal projects, etc.

Remote-First

One thing to know about Trail of Bits is that we have always been, and always will be, a remote-first company — “remote” is not a skill we added for the pandemic. That means that we are global in nature, and asynchronous by design. We’ve fostered a collegial atmosphere, one with close, intimate collaboration among colleagues.

Those of us who work here wouldn’t have it any other way.

At its heart, the art of asynchronous collaboration is about understanding the work, understanding our tasks, and asking clear questions that request actionable replies from our expert coworkers. It works. We believe that, according to the criteria described in “The Five Levels of Remote Work”, we are somewhere between levels four and five.

For example, we consider carefully when we need face-to-face meetings, to avoid the “this-meeting-could-have-been-handled-in-a-Slack-conversation” problem that plagues a lot of companies. When we do meet face-to-face, we use Google Meet; the meetings all have a written agenda, are recorded, and have notes taken and distributed to all attendees.

We have a minimal reliance on email for internal conversations, preferring the more secure and archived Slack as the primary chat and discussion forum. We strongly recommend that Slack is used with Notifications Off. We also do not require Slack to be installed on your mobile phone – in fact we suggest that you don’t – so you’re not tempted or compelled to check Slack during your time off (also, all personal mobile devices are required to run MDM if they handle any work data). Each project – whether formal or ad-hoc – has a dedicated Slack channel. Slack communications are written with the expectation that people have limited time, hence our focus on well-considered (and considerate) messages that come quickly to the point and make actionable requests for collaboration.

We use Trello and GitHub to visually collaborate on projects and a range of other purpose-built tools to reduce toil and encourage meaningful collaboration without getting all up in your grill.

Work Hours and Work-Life Balance

We expect you to maintain a good, healthy, and enjoyable balance between your personal time and work time — see that example above: we don’t want you using Slack as you lie in bed! Since you already have a desk in your house, wait until you get to your desk to turn on Slack and start work. You’ll find that we’re quite insistent that you turn off during your time off — recharge, refresh, and hit the ground running when you are back.

To that end, we have generous programs to set yourself up at home, like a $1,000 stipend to set up your home office, a $500 a year personal learning and development budget, a co-working space option, 20 days of paid time off and 15 company holidays per year, and more. See this page for more information.

Set Your Hours: A Typical Day

We are a results-oriented company, and we are less concerned with when you work than with the impact your work has on the company. So a typical day can look like this:

Morning (9am-noon)

We recommend certain practices to begin your day, to draw a distinction between home-life and work. For example, we recommend establishing a commute even if you work in your own home. You can pull up recordings of any meetings from earlier in the week, read some messages a colleague left you overnight, and check for next-best priorities on Github Issues. You meet on Google Meet for a quick standup and see how things are going. You can see it on their face as clear as day — everyone at Trail of Bits has high-end audio/video equipment — they’re excited about a monster new attack surface they found yesterday.

Afternoon (noon-3pm)

Maybe you’d visited a doctor in the beginning of the week, so today you’re working a couple of extra hours to time-shift. You’ve got a lunchtime invite to attend a lunch-and-learn, find it on the company-wide team meetings calendar and pop in. One of our Team Leads is reviewing an academic paper on such and such, and Sam Moelius is absolutely destroying him with extremely simple and polite questions. You file an issue you discovered by hand this morning into Github Issues. Document a few more security properties, these will be great for our fuzzer later this afternoon. It’s easy to focus because you followed the company-recommended advice to disable all but the most essential Slack notifications. But since your collaborator is a few timezones ahead, you pop out to run an errand before the stores close.

Evening (3-7pm)

You take a walk outside for coffee (“stupid little mental health walk”). Exercise and sun are good for the mind. Those properties you found this morning could result in excellent bugs if they break the project. You spend the rest of the evening writing them up into dylint/echidna/libFuzzer … whatever. You login to your dev machine over Tailscale/locally in VM/on DigitalOcean, and start a batch fuzzer job that will complete in the morning. You write a brief note on Slack to let your coworker know where things are and that you’re signing off for the night. You close the lid on your laptop, and you don’t have Slack installed on your phone. Time to raid a dungeon in Elden Ring!

Next week, you have IRAD planned to take the lessons learned from this project and incorporate them into the company’s new Automated Testing Handbook.

More questions?

Get in touch. Visit https://trailofbits.com/careers, or use our contact form.

The Trail of Bits Hiring Process

When engineers apply to Trail of Bits, they’re often surprised by how straightforward and streamlined our hiring process is. After years of experience, we’ve cut the process to its bedrock, so that it’s candidate focused, quick, and effective.

Here’s a short video showing some of our European colleagues discussing some cool things they’re working on now:

Our Interview Process

The process from interview to offer is in four parts, and the whole thing can take three weeks or less. We want to be respectful of your time—we won’t advance you in the process unless we think there’s a good reason to continue, and we ask you to do the same.

Here’s a short video showing some of our European colleagues describing the Trail of Bits interview process:

In a Nutshell

  1. Initial screen (~30 minutes, one-on-one)
  2. Assessment (2 hours, on your own)
  3. Final interview (~2 hours, with two engineers and a team or practice lead)
  4. Decision (within five business days) and offer letter or pass with explanation (we often recommend that candidates reapply in the future)

Initial Screen

We start our process with a 30-minute screening call, designed to assure a rough match of mission, skill, and capability. These calls are typically with a Trail of Bits recruiter, or the hiring manager for the position.

Assessment

Those making it through the screen are given a brief, take-home assessment, on which we want you to spend two hours or less. Interviews are only ever so good, and there’s a limit to what you can get across on a phone or video call. We want to see what you can do! Some people have a work portfolio, but even in many of those cases, we want to watch you work. So we prepared short assessments that we’ve benchmarked to only take approximately two hours. The assessment is technically focused and allows us to see your skills in practice. The assessment is reviewed by a lead engineer in the appropriate practice—cryptography, blockchain, application security, research, or engineering. In some cases, in place of the assessment, we are happy to accept a work sample you have already put together.

Final Interview

Those making it through the assessment are invited to the final interview, where the real matchmaking is done. Now, whether you provided a work sample or completed an assessment assignment we send you, if it got you past that hurdle and into this final interview, that’s something to talk about! We find that the best way to start our final interviews is right there, because in fact this is something you are rightfully proud of. Tell us about it, and how you approached the issue, the problems you faced while doing it and go ahead and brag a little! This is a perfect way to start a conversation about what it would be like if you worked here.

Our final interviews are about two hours in length—some are shorter, some longer, but it’s around there on average. You can expect a conversation with two to three peers, about a range of deeply technical subjects to assess whether this is a good alignment for us all. There are no trick questions, just a collegial approach to solving technical problems similar to those we face every day.

Your turn

A healthy portion of the final interview—about 20%—is dedicated to answering your questions about us. We’re very up-front about what it’s like to work with us.

Decision

Within five business days, you should receive either an offer letter, or an email explaining why we decided not to move forward with your candidacy. In many cases, we recommend that you reapply in the future. For example, when you get more experience in an area we felt you needed more depth in, or after you’ve developed some specific skills we mentioned during the process. But in all cases we will be open and communicative.

A sample of a Trail of Bits rejection letter from our Blockchain team

 

A sample of a rejection email from our cryptography team

Negotiating and acceptance

Our offer will be well-considered and based on the conditions and criteria we know to exist. If there are other factors you feel we have not taken into account, please do feel free to reply and negotiate. You’ll find us reasonable—at this point we want you to work with us as much as you want to work with us, so we make efforts to meet your expectations wherever we can.

During the interview process we’ll ask—or you’ll tell us—what your availability will be, so at the offer stage we will propose a start date. If you’re planning to accept an offer with us, we always recommend you take some extra time off between jobs. We advocate for it. If you need a different start date—for example, if you need more time to give notice, to finish some personal business prior to joining us, or even if you want to start sooner than we’d thought—we will do our best to accommodate your needs.

All paperwork is sent digitally and once it’s all signed, we work with you to get you all the equipment that you need. We also provide a virtual Ramp credit card for other onboarding expenses that we’re happy to cover (more on that in Onboarding, below).

Starting at Trail of Bits

Once you accept and sign your offer letter, we’ll provide you with the documentation you’ll need to have the most successful (and enjoyable!) onboarding experience. From items like payroll and benefits to our operating practices and procedures, you’ll find our documentation and resources are quite comprehensive. The first things you can expect to find are:

  • Onboarding checklist
  • Payroll and benefits enrollment steps
  • Employee handbook
  • Handbook for the practice you are joining (e.g., Assurance, Engineering, Project Management Organization, Operations, etc.)
  • Handbook for the team you are joining (e.g., Application Security, Technical Editing, etc.)
  • Compensation philosophy
  • Learning & development resources

Our Learning & Development Resources document, for example, contains a detailed and actionable list of resources that each Trail of Bits engineer and non-engineer can use to further their career and personal development goals. From books we think you should read to presentations—ours and those of others—you should watch, to references on specific courses we think are great for all of us. Managers will find guides to better leadership, all employees will find access to online classes and courses, and interns can benefit from tips and tricks lists. And engineers will love that we regularly schedule software development and skills-based training for the team and send individuals to targeted training for areas we intend to grow and specialize in.

Equipment

We outfit every employee with the top kit they need to work remotely (and securely!). Engineers at Trail of Bits currently receive the latest generation 14 or 16″ Macbook Pro with 64 GB of RAM, and Operations team members receive the latest generation 13″ Macbook Pro with 24 GB of RAM. Depending on your home country, this will either be ordered to arrive before your start date, or we will send you a Ramp card to buy the items in your home country. We will also order a YubiKey 5C and 5Ci, a high-end Logitech C925e or Brio webcam, and one of our standard headsets (typically, a Sennheiser Game One) to arrive before your first day. Your Ramp card is also loaded with extra cash to upgrade your home office (we recommend Dell U2723QE or Dell U3223QE monitors, a CalDigit TS4 Plus dock, or even a new router like the Eero Pro 6E). There’s lots more information in our onboarding guide, which you’ll receive when you join!

More questions?

Get in touch. Visit https://trailofbits.com/careers, or use our contact form.

Managing risk in blockchain deployments

Do you need a blockchain? And if so, what kind?

Trail of Bits has released an operational risk assessment report on blockchain technology. As more businesses consider the innovative advantages of blockchains and, more generally, distributed ledger technologies (DLT), executives must decide whether and how to adopt them. Organizations adopting these systems must understand and mitigate the risks associated with operating a blockchain service organization, managing wallets and encryption keys, relying on external providers of APIs, and many other related topics. This report is intended to provide decision-makers with the context necessary to assess these risks and plan to mitigate them.

In the report, we cover the current state, use cases, and deficiencies of blockchains. We survey the common pitfalls, failures, and vulnerabilities that we’ve observed as leaders in the field of blockchain assessment, security tooling, and formal verification.

Blockchains have significantly different constraints, security properties, and resource requirements than traditional data storage alternatives. The diversity of blockchain types and features can make it challenging to decide whether a blockchain is an appropriate technical solution for a given problem and, if so, which type of blockchain to use. To help readers make such decisions, the report contains written and graphical resources, including a decision tree, comparison tables, and a risk/impact matrix.

Should you use a blockchain?

A decision tree from the Trail of Bits operational risk assessment on blockchains

Goldman Sachs partnered with Trail of Bits in 2018 to create a Cryptocurrency Risk Framework. This report applies and updates some of the results from that study. It also includes information included in a project that Trail of Bits completed for the Defense Advanced Research Projects Agency (DARPA) to examine the fundamental properties of blockchains and the cybersecurity risks associated with them.

Key insights

Here are some of the key insights from our research:

  • Proof-of-work technology and its risks are relatively well understood compared to newer consensus mechanisms like proof of stake, proof of authority, and proof of burn.
  • The foremost risk is “the storage problem.” It is not the storage of cryptocurrency, but rather the storage of the cryptographic private keys that control the ownership of an address (account). Disclosure of, or even momentary loss of control over, the keys can result in the complete and immediate loss of that address’s funds.
    • Specialized key-storing hardware, either a hardware security module (HSM) or hardware wallet, is an effective security control when designed and used properly, but current hardware solutions are less than perfect.
    • Compartmentalization of funds and multisignature wallets are also effective security controls and complement the use of HSMs.
  • Security breaches or outages at third-party API providers represent a secondary risk, which is best mitigated by contingency planning.
  • Centralization of mining power is a systemic risk whose impact is less clear but important to monitor; it represents a potential for blockchain manipulation and, therefore, currency manipulation.
  • Most blockchain software, though open source, has not been formally assessed by reputable application-security teams. Commission regular security reviews to assess blockchain software for traditional vulnerabilities. Use network segmentation to prevent blockchain software from being exposed to potentially exploitable vulnerabilities.

It is our hope that this report can be used as a community resource to inform and encourage organizations pursuing blockchain strategies to do so in a manner that is effective and safe.

This research was conducted by Trail of Bits based upon work supported by DARPA under Contract No. HR001120C0084 (Distribution Statement A, Approved for Public Release: Distribution Unlimited). Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the United States Government or DARPA.

Are blockchains decentralized?

A new Trail of Bits research report examines unintended centralities in distributed ledgers

Blockchains can help push the boundaries of current technology in useful ways. However, to make good risk decisions involving exciting and innovative technologies, people need demonstrable facts that are arrived at through reproducible methods and open data.

We believe the risks inherent in blockchains and cryptocurrencies have been poorly described and are often ignored—or even mocked—by those seeking to cash in on this decade’s gold rush.

In response to recent market turmoil and plummeting prices, proponents of cryptocurrency point to the technology’s fundamentals as sound. Are they?

Over the past year, Trail of Bits was engaged by the Defense Advanced Research Projects Agency (DARPA) to examine the fundamental properties of blockchains and the cybersecurity risks associated with them. DARPA wanted to understand those security assumptions and determine to what degree blockchains are actually decentralized.

To answer DARPA’s question, Trail of Bits researchers performed analyses and meta-analyses of prior academic work and of real-world findings that had never before been aggregated, updating prior research with new data in some cases. They also did novel work, building new tools and pursuing original research.

The resulting report is a 30-thousand-foot view of what’s currently known about blockchain technology. Whether these findings affect financial markets is out of the scope of the report: our work at Trail of Bits is entirely about understanding and mitigating security risk.

The report also contains links to the substantial supporting and analytical materials. Our findings are reproducible, and our research is open-source and freely distributable. So you can dig in for yourself.

Key findings

  • Blockchain immutability can be broken not by exploiting cryptographic vulnerabilities, but instead by subverting the properties of a blockchain’s implementations, networking, and consensus protocols. We show that a subset of participants can garner undue, centralized control over the entire system:
    • While the encryption used within cryptocurrencies is for all intents and purposes secure, it does not guarantee security, as touted by proponents.
    • Bitcoin traffic is unencrypted; any third party on the network route between nodes (e.g., internet service providers, Wi-Fi access point operators, or governments) can observe and choose to drop any messages they wish.
    • Tor is now the largest network provider in Bitcoin; just about 55% of Bitcoin nodes were addressable only via Tor (as of March 2022). A malicious Tor exit node can modify or drop traffic.
  • More than one in five Bitcoin nodes are running an old version of the Bitcoin core client that is known to be vulnerable.
  • The number of entities sufficient to disrupt a blockchain is relatively low: four for Bitcoin, two for Ethereum, and less than a dozen for most proof-of-stake networks.
  • When nodes have an out-of-date or incorrect view of the network, this lowers the percentage of the hashrate necessary to execute a standard 51% attack. During the first half of 2021, the actual cost of a 51% attack on Bitcoin was closer to 49% of the hashrate—and this can be lowered substantially through network delays.
  • For a blockchain to be optimally distributed, there must be a so-called Sybil cost. There is currently no known way to implement Sybil costs in a permissionless blockchain like Bitcoin or Ethereum without employing a centralized trusted third party (TTP). Until a mechanism for enforcing Sybil costs without a TTP is discovered, it will be almost impossible for permissionless blockchains to achieve satisfactory decentralization.

Novel research within the report

  • Analysis of the Bitcoin consensus network and network topology
  • Updated analysis of the effect of software delays on the hashrate required to exploit blockchains (we did not devise the theory, but we applied it to the latest data)
  • Calculation of the Nakamoto coefficient for proof-of-stake blockchains (once again, the theory was already known, but we applied it to the latest data)
  • Analysis of software centrality
  • Analysis of Ethereum smart contract similarity
  • Analysis of mining pool protocols, software, and authentication
  • Combining the survey of sources (both academic and anecdotal) that support our thesis that there is a lack of decentralization in blockchains

The research to which this blog post refers was conducted by Trail of Bits based upon work supported by DARPA under Contract No. HR001120C0084 (Distribution Statement A, Approved for Public Release: Distribution Unlimited). Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the United States Government or DARPA.

Announcing the new Trail of Bits podcast

Trail of Bits has launched a podcast. The first five-episode season is now available for download. The podcast and its RSS feed are available at trailofbits.audio, and you may subscribe on all major podcast outlets, including Apple iTunes, Spotify, Gaana, Google Podcasts, Amazon Music, and many others.

Listening to our podcast is like having a couple of friends—who happen to be the world’s leading cybersecurity experts—explain to you how they protect some of the world’s most precious data, in plain, straightforward English. Each episode provides entertaining, plain-language descriptions of the exciting technologies and projects that Trail of Bits engineer-consultants are working on. The podcast is designed to be simple (yet not dumbed-down), technically accurate, and really fun to listen to. And the only ads you’ll ever hear are for our free and open source software and tools.

Our audience includes tech-savvy and technically curious people who want to learn more about the trends at technology’s leading edge:

Early adopters, architects, technical professionals, and the technically fascinated who want to know more about trends that are occurring at the forward edge of the technology adoption curve

Technology executives who want a solid, high-level understanding about the trends and technologies that they face in the marketplace, without getting dragged into the weeds

Journalists and reporters who cover technology and want primers to serve as context for the stories for which they have to explain complex technical concepts to a mainstream audience

Season one, released in June of 2022, comprises five episodes:

  1. Zero Knowledge Proofs and ZKDocs. Using the procedures described in well-known academic papers, software developers around the world implemented certain complicated encryption schemes for banks and exchanges to protect billions of dollars. But the procedures the developers followed had a fatal flaw. Those billions of dollars were suddenly an easy target for criminal and nation-state hackers. Fortunately for all of us, there’s a guy named Jim. This episode features Trail of Bits Cryptography Team Lead Jim Miller and a guest appearance by Matthew D. Green.
  2. Immutable. Here’s something lots of people like about Bitcoin: Governments can’t control it. You can spend your Bitcoin the way you want to, and nobody can stop you. But here’s the bad news: That’s not true. It turns out that one of the things everybody believes and likes about cryptocurrency is actually wrong. Really wrong. About a year ago, Trail of Bits was engaged by DARPA, the Defense Advanced Research Projects Agency, to answer a question: Are blockchains really decentralized? This is a key question for cryptocurrencies. And in this episode, we explain what the Trail of Bits team found. This episode features Trail of Bits CEO Dan Guido, Principal Engineer Evan Sultanik, and Research and Engineering Director Trent Brunson.
  3. Internships and Winternships. Meet the Trail of Bits interns who represent the next generation of security engineers. They’re creating new tools that will be used by software developers around the world and updating existing tools to optimize their efficiency. Trail of Bits considers building a pipeline of talented engineers to be strategic-and we start by encouraging students while they are still in high school. This episode features CEO Dan Guido, interns Suha Hussain and Sam Alws, and guest appearances by Jason An, Clarence Lam, Harikesh Kailad, and Patrick Zhang of the Montgomery Blair High School Cybersecurity Club.
  4. It-Depends. Most people imagine software engineers tapping keyboards in a kombucha-keg-filled room. But modern software isn’t written… It’s assembled. Developers write code, but they don’t start from scratch. They use open-source code and libraries developed by a community. Those building blocks themselves depend on other pieces of open-source software, which are built atop yet others, and so on. The dependencies of this software supply chain are, therefore, recursive-“nested,” like a Russian matryoshka doll. So when you ask whether your software is safe, the answer is, “It Depends.” This episode features Trail of Bits engineers Evan Sultanik and William Woodruff and guest appearances by Patrick Gray, Clint Bruce, Eric Olson, and Allan Friedman.
  5. Future. Companies that make high-assurance software—programs whose failure means catastrophic consequences like the disappearance of a billion dollars or the explosion of a rocket ship on the launch pad—are adopting technologies that are a couple of years ahead of the mainstream. When you ask a Trail of Bits engineer about what’s happening, you’re talking to someone who is already operating in the future. In this episode, Trail of Bits engineers discuss trends they are seeing now that the rest of the industry will see in the next 18 to 24 months. This episode features Trail of Bits CEO Dan Guido and engineer-consultants Opal Wright, Nat Chin, Josselin Feist, and Peter Goodman.

Producers Dan Guido and Nick Selby (who leads the Software Assurance Practice at Trail of Bits and who narrates the series) believe that the key to a great technology podcast is high production values: high-quality sound, music, and sound design that support great storytelling. They did not want this to be a “three-guys-sitting-around-a-microphone-talking” kind of podcast. To that end, Trail of Bits partnered with two world-class long-form storytellers with decades of experience in radio and podcast production:

  • Chris Julin has spent years telling audio stories and helping other people tell theirs. These days, he works as a story editor and producer for news outlets like APM Reports, West Virginia Public Broadcasting, and Marketplace. He has also taught and mentored hundreds of young journalists as a professor. For the Trail of Bits podcast, he serves as a story and music editor, sound designer, and mixing and mastering engineer. He also composed our theme song.
  • Emily Haavik has worked as a broadcast journalist in radio, television, and digital media for the past 10 years. She’s spent time writing, reporting, covering courts, producing investigative podcasts, and serving as an editorial manager. She previously worked for APM Reports and KARE 11 TV before becoming a freelance writer and audio producer. She also fronts an Americana band called Emily Haavik & the 35s. For the Trail of Bits podcast, she is a script-writer and interviewer who works with story concepts and an audio producer and editor.

Distribution

With the exception of any copyrighted music contained in episodes, the Trail of Bits podcast is Copyright © 2022 by Trail of Bits and licensed under Attribution-NonCommercial-NoDerivatives 4.0 International. This license allows reuse: Reusers may copy and distribute the material in any medium or format in unadapted form and for noncommercial purposes only (noncommercial means not primarily intended for or directed toward commercial advantage or monetary compensation), provided that reusers give credit to Trail of Bits as the creator. No derivatives or adaptations of this work are permitted. To view a copy of this license, visit http://creativecommons.org/licenses/by-nc-nd/4.0/.

About us

Since 2012, Trail of Bits has helped secure the world’s most targeted organizations and products. We combine high-end security research with a real-world attacker mentality to reduce risk and fortify code.

Themes from PyCon US 2022

By Adam Meily

After two long years of lockdowns, virtual meetups, quarantines, and general chaos, the Python community gathered en masse to Salt Lake City for PyCon 2022. Two of our engineers attended the conference, and we are happy to report that the Python community is not only alive and well but also thriving, with multiple speakers showing off projects they worked on during the pandemic.

Here are some of the themes and highlights we enjoyed!

Supply chain security

How PyPI Survives the Coming Zombie Apocalypse

Supply chain attacks and bad actors are an active threat for the entire world. Installing a malicious package can have devastating impacts on organizations and everyday people. The Python Package Index (PyPI) maintainers are actively working to provide additional protections and security for the Python supply chain. Protections cover both the package maintainer with additional authentication security and the user downloading the package through new verification and trust techniques built directly into the platform.

Dustin Ingram detailed how PyPI is adopting new security measures that greatly improve the security and trust of the entire PyPI platform. Several of the enhancements within PyPI and related tooling were thanks in large part to our senior engineers Will Woodruff and Alex Cameron, who received a special thanks during the presentation.

  • pip-audit, a new tool that can identify vulnerable dependencies in Python applications.
  • A new sigstore client for Python, allowing ordinary uses to sign for and verify signatures on Python packages.
  • Two-factor authentication will be required for packages that are important to the community and PyPI itself, and other package authors will have the ability to opt-in to 2FA in the near future.
  • With credential-less publication using OpenID Connect integration, you will soon be able to publish packages, without credentials, directly from GitHub Actions using a simple configuration setting.
  • Signed package metadata (PEP 458) and a PyPI disaster recovery plan (PEP 480) provide security and trust for both everyday users and recovery from catastrophic events.

Also, Ashish Bijlani presented a new tool called Packj that tests packages within PyPI to identify behaviors that may add risk to applications and checks whether its metadata and code may be malicious.

Recent Python successes

Since release 3.9, Python has switched to a yearly release schedule (PEP 602), which ensures that new features are regularly being added to the language to keep it modern.

Annotations: Documenting code with code

The first day’s keynote was from Łukasz Langa, who encouraged everyone to use annotations in new code, add them to existing code, and to take advantage of the modern annotation syntactic sugar. Why? Because ugly type annotations hint at ugly code.

Annotations improve code readability and empower IDEs and static code analyzers to identify issues before they are encountered at runtime. With modern syntactic sugar, writing annotations is easier than ever, including:

  • Using built-in container types in annotations (PEP 585). No more typing.List[] or typing.Dict[], just use list[] and dict[].
  • Replacing the Union type (PEP 604) with the or operator, |. No more typing.Union[].
  • Creating distinct types to provide meaning, thus making code more readable. For example: If a function accepts a str argument, can it be any string? Can it be a blob of text or a single word? Type aliases and the NewType construct are zero-runtime overhead and can easily be added to convey meaning for users and improve static type-checking results.

Pattern matching

Python 3.9 gained a powerful pattern matching mechanism and the author of the original pattern matching PEP provided a talk detailing the history, implementation, and future of pattern matching. Brandt Bucher gave an overview of the PEP process, which included four different PEPs of different scope and target audience:

  • PEP 622 – Initial discussion. This original PEP proved to be too all encompassing so it was broken down into three smaller PEPs.
  • PEP 634 – Specification, intended for the implementers
  • PEP 635 – Motivation and Rationale, intended for the steering council
  • PEP 636 – Tutorial, intended for the end-user

Pattern matching is not a switch statement! It provides optimizations at the bytecode and interpreter level over the traditional if/elif/else pattern.

The design and implementation was influenced by established standards in other languages such as Rust, Scala, and Haskell, with some Python syntax magic included. Pattern matching is a very exciting development with some future work coming that will make it even more powerful and performant.

Python in space!

The second day’s keynote by Sara Issaoun described how Python was a critical component of reconstructing the famous first image of a black hole. Sara went into the details of using the entire earth as a massive satellite dish to capture petabytes of data and then developing optimized data analysis pipelines in Python to transform all the data to an image that is only a couple kilobytes. This is perhaps the largest dataset ever processed in history and it was done primarily in Python.

Credit: Event Horizon Telescope Collaboration

Many of us have seen this famous image, but knowing that Python played a central role in making it provides more perspective and appreciation for the language. Python is helping answer some of the most important questions in science. On May 12, the first images of the massive black hole at the center of our very own Milky Way galaxy were revealed. Python was again a major component of bringing the images of Sagittarius A* to the world.

Tooling ecosystem

There are so many tools within the Python ecosystem that make the process of development, testing, building, collaboration, and publishing easier or automated.

Binary extensions on easy mode

Building and packaging binary extensions can be cumbersome and may require developers to write extensions in C using the CPython API. There have been several improvements by the community that add more options to building and deploying binary extensions.

Henry Schreiner III provided a deep-dive into several packages and methods to make the process of building binary extensions easier.

  • pybind11 is a header-only API to write Python extensions in C++, which makes integrating C++ code and libraries easier.
  • scikit-build allows projects to build their binary extensions with CMake, rather than the setuptools or distutils method.
  • cibuildwheel package makes building and testing wheels with binary extensions easy whether with CI or locally.

Open-source maintenance on autopilot

For managing all of the un-fun parts of project maintenance, John Reese gave a talk on tips and tricks for automating all of the necessary but tedious tasks when leading an open-source project.

Time is the only resource we can’t buy. With this in mind, John offered multiple guidelines that can make the maintenance and contribution processes easier.

  • Use a pyproject.toml file to define well-formed metadata about the project.
  • Provide a well-defined list of dependencies. Versions should not be so specific that developers using the package encounter version conflicts with other dependencies. And the versions should not be so generic that incompatibilities can be introduced silently after upgrading dependencies.
  • Create reproducible and automated development workflows starting from initial setup to building, testing, and publishing. Performing a release should be as easy as possible to keep pace with the user’s needs.
  • Introduce automated code quality checks and code formatting to identify bugs and potential issues early and remove the guess-work around code style.
  • Write accessible documentation that includes expectations for contributors.

The future is bright

Python, now with browser OS support

Saturday’s keynote speaker, Peter Wang, introduced an alpha version of PyScript—Python running entirely in the browser with support for interacting with the DOM and JavaScript libraries. The web browser has silently won the OS wars and putting Python in the browser will make it even more approachable for new users.

Several demos were shown that exercised core Python functionality, such as a REPL session, and HTML capabilities such as manipulating the DOM and a simple ToDo application. More advanced demonstrations show how Python can now be used in conjunction with the popular data visualization library d3 and create interactive 3D animations with WebGL. All of this can be done with Python running within the browser, and in most cases, within a single HTML file.

To show the full power of PyScript, Peter played Super Mario in the browser, controlling Mario with hand gestures and computer vision, all in Python, which was a huge crowd pleaser. PyScript is pushing the envelope of Python and future-proofs the language for new platforms and architectures.

Python and the need for speed

Every Python developer, at some point, has been asked the question, Isn’t Python Slow? With performance-optimized packages such as NumPy and Pandas, Python has proven that it’s fast enough to solve some of the most complex problems (see The counter-intuitive rise of Python in scientific computing). But, as an interpreted language, there is still work to be done to decrease the interpretation overhead and improve overall performance.

The upcoming Python 3.11 release will have the first set of performance improvements from CPython maintainers, who are using Anaconda’s Pyston and Instagram’s Cinder as guides for improvement.

As Kevin Modzelewski detailed in his talk, there are patterns that developers can start adopting today that will take advantage of new optimizations as they become available in future releases. In the past, optimizations have been difficult to implement because of the dynamic nature of Python. For example, performing an attribute lookup on an attribute set in the init() versus one set dynamically via setattr(), had the same performance cost. As a developer, you get dynamic features at zero cost.

However, these truly dynamic features are used much less frequently than traditional programming practices. So one of the approaches for speeding up CPython is to optimize for static use cases and allow the truly dynamic cases to be slower and have costs associated with them. Now, with this principle that prioritizes static code practices, static lookups can be cached and optimized while dynamic features can be slower since they occur much less frequently.

Here’s what developers can do to prepare for CPython’s new optimizations:

  • Do not reassign global variables. Set once and reference or mutate. This will take advantage of the new lookup cache.
  • Keep objects the same shape with the same attributes. Use flag attributes instead of conditionally setting attributes so that attribute lookups take advantage of the new lookup cache.
  • Call methods directly on objects rather than locally caching the method. With attribute lookups optimized, this replaces the traditional wisdom of caching a method prior to using it repeatedly within a loop.
  • Traditional advice is to move performance-critical code to C to see significant improvements, however, this may not be the case going forward. All of the optimizations so far can only be taken advantage of within Python code. So, C code will not have the same optimizations, at least for now.

Closing thoughts

In addition to some amazing technical developments and discoveries discussed at PyCon 2022, there are several intangibles that made the conference enjoyable. Everyone was extremely kind, helpful, and courteous. Speakers used inclusive language and the entire event felt welcoming to non-technical folks, beginners, and experts alike. The wide array of topics, booths, and events made sure there was something for everyone. And the Salt Lake City Convention center was a great spot to host PyCon 2022 with plenty of room for talks with so many great restaurants within a short walking distance.

PyCon 2022 really felt like both a return to normalcy for the community and a breakthrough moment for Python to not only remain one of the most popular programming platforms across a wide variety of industries but also grow its already massive community and use case. As the closing keynote speaker Naomi Ceder so eloquently put it, the Python community, and entire open source model, is built upon a culture of gift giving. The common saying is that Python is a language that comes with “batteries included,” which, upon reflection, is only true because so much of the community has given the gift of their time, their work, and their expertise. Thanks to everyone for a fantastic PyCon 2022!

Interactive decompilation with rellic-xref

By Francesco Bertolaccini

Rellic is a framework for analyzing and decompiling LLVM modules into C code, implementing the concepts described in the original paper presenting the Dream decompiler and its successor, Dream++. It recently made an appearance on this blog when I presented rellic-headergen, a tool for extracting debug metadata from LLVM modules and turning them into compilable C header files. In this post, I am presenting a tool I developed for exploring the relationship between the original LLVM module and its decompiled C version: rellic-xref.

rellic-xref’s interface

rellic-xref

I was tasked with improving the quality of the “provenance information” (i.e., information about how each LLVM instruction relates to the final decompiled code) produced by Rellic. However, the main front end for Rellic (a tool called rellic-decomp that produces C source code in a “batch processing” style) does not give much information about what is happening under the hood. Most importantly, it does not print any of the provenance info I was interested in.

To solve this problem, I developed rellic-xref as a web interface so that Rellic can be used in an interactive and graphical way. rellic-xref spins up a local web server and serves as an interface to the underlying decompiler. When a user uploads an LLVM module, a textual representation of the module is presented in the right-hand pane. The user can then run a variety of preprocessing steps on the LLVM bitcode or proceed to the decompilation step. Preprocessing is sometimes required when the module contains instructions that are not yet supported by the decompilation engine.

Once the module has been decompiled, the original module and decompiled source code are shown side by side:

Original module and decompiled source code

The main attraction of the tool is already available at this point: hovering your mouse over parts of the decompiled source code will highlight the instructions that led to its generation, and vice versa.

The refinement process

The source code that’s produced straight out of the decompiler is not quite as pretty as it could be. To fix this, Rellic offers a series of refinement passes that make the code more readable. These refinement passes are normally executed iteratively, and the order in which these passes are executed is hard-coded in rellic-decomp. For example, pressing the “Use default chain” button loads rellic-decomp’s default pass configuration into rellic-xref.

Refinement passes offered by Rellic

The default chain consists of passes that are executed only once and passes that are computed iteratively to search for a fixed point. However, rellic-xref gives users the ability to change the order and the way in which the refinement passes are run: passes can be removed (using the “x” buttons in the figure above) and inserted at will.

Although the Rellic passes operate on the Clang abstract syntax tree (AST), they are not suitable for any generic C program, as they rely on assumptions about how the decompilation process generates them. In particular, the decompiled code is initially in a form similar to single static assignment (SSA), reflecting the fact that it is directly generated from LLVM bitcode, which is itself in SSA form.

Refinement passes

For those who are unfamiliar with Rellic’s refinement passes, we provide descriptions of these passes followed by an example of how they refine the code.

Dead statement elimination
This pass removes statements from the AST that do not cause any side effects. For example, “null” statements (lone semicolons) and several types of expressions can be safely removed.

Original Refined

void foo() {

int a;

a = 3;

a;

bar(a);

}

void foo() {

int a;

a = 3;

bar(a);

}

Z3 condition simplification
This pass uses the Z3 SMT solver to improve the quality of if and while conditions by reducing their size as much as possible. It works in a recursive manner by inspecting the syntax tree of each condition and pruning any branch that it finds to be trivially true or false.

Original Refined

if(1U && x == 3) {

foo(x);

}

if(x == 3) {

foo(x);

}

if(x != 3 || x == 3) {

foo(x);

}

if(1U) {

foo(x);

}

Nested condition propagation
As the name suggests, this pass propagates conditions from parent statements to their children. In practical terms, this means that conditions in parent if and while statements are assumed to be true in nested if and while statements.

Original Refined

if(x == 0) {

if(x == 0 && y == 1) {

bar();

}

}

if(x == 0) {

if(1U && y == 1) {

bar();

}

}

Nested scope combination
This one is pretty simple: any statement that appears in a compound statement or in a trivially true if statement can be extracted and put into the parent scope. This pass works on the assumption that all local variables have been declared at the beginning of the function.

Original Refined

void foo() {

int x;

int y;

{

x = 1;

}

if(1U) {

y = 1;

}

}

void foo() {

int x;

int y;

x = 1;

y = 1;

}

Condition-based refinement
This pass recognizes when a scope contains two adjacent if statements that have opposite conditions and merges them into an if-else statement.

Original Refined

if(a == 42) {

foo();

}

if(!(a == 42)) {

bar();

}

if(a == 42) {

foo();

} else {

bar();

}

Reachability-based refinement
Similar to the condition-based refinement pass, this one recognizes when successive if statements have exclusive but not opposite reaching conditions and rearranges them into if-else-if statements.

Original Refined

if(a == 42) {

foo();

}

if(!(a == 42) && b == 13) {

bar();

}

if(a == 42) {

foo();

} else if(b == 13) {

bar();

}

Loop refinement
This pass recognizes if statements that should be responsible for terminating infinite while loops. It refactors the code to create loops with conditions.

Original Refined

while(true) {

if(a == 42) {

break;

}

foo();

}

while(!(a == 42)) {

foo();

}

Expression combination
This pass performs a number of simplifications, such as turning pointer arithmetic into array accesses and removing superfluous casts.

Original Refined
*&x
x
!(x == 5)
x != 5
(&expr)->field
expr.field

Condition normalization
This is the only pass that is not used in the default refinement chain. The purpose of this pass is to turn conditions into conjunctive normal form to reveal more opportunities for simplification. Unfortunately, it also tends to produce exponentially large conditions—literally!—so it is best used sparingly and only as a very last step before applying a final simplification using Z3.

I’m sold! How do I use it?

Just follow the instructions in the README and you’ll have an instance of rellic-xref running in no time.

Closing thoughts

rellic-xref turns the traditionally batch-oriented Rellic into a more interactive tool that provides insight into the decompilation and refinement process. It is also a glimpse into what the Rellic framework could be used for. For instance, what if the user had more control over the underlying Clang AST? Allowing custom variable renaming and retyping, for example, would go a long way in making Rellic feel like a proper component of a reverse engineering suite. Further work on rellic-xref (or development of a similar tool) could give users more control over the Clang AST in this way.

Rellic’s passes operate directly at the C AST level and heavily use Clang’s APIs. This was both a blessing and a curse as I worked with Rellic. For instance, calling the Clang AST “abstract” is a bit of a misnomer, as it has characteristics of both an abstract and a concrete syntax tree. For example, it contains information about positions of tokens and comments but also things that are not actually present in the source code text, like implicit casts. My experience with Rellic has taught me that the Clang AST interface is not really meant to be used as a mutable resource, and it has more of a write-once, read-many semantics. We have plans to migrate Rellic for use in an upcoming project featuring MLIR, which may help in this regard. However, that is beyond the scope of this blog post.

I’d like to thank my mentor, Peter Goodman, for his guidance during my internship and Marek Surovič for his precious feedback on my work with Rellic. Working at Trail of Bits continues to prove to be a great experience full of gratifying moments.

Themes from Real World Crypto 2022

By William Woodruff

Last week, over 500 cryptographers from around the world gathered in Amsterdam for Real World Crypto 2022, meeting in person for the first time in over two years.

As in previous years, we dispatched a handful of our researchers and engineers to attend the conference, listen to talks, and schmooze observe the themes currently dominating the nexus between cryptographic research and practical (real world!) engineering.

Here are the major themes we gleaned from Real World Crypto 2022:

  1. Trusted hardware isn’t so trustworthy: Implementers of trusted hardware (whether trusted execution environments (TEEs), HSMs, or secure enclaves) continue to make engineering mistakes that fundamentally violate the integrity promises made by the hardware.
  2. Security tooling is still too difficult to use: Or “you can lead a horse to water, but you can’t make it run ./configure && make && make install.”
  3. Side channels everywhere: When God closes a door, he opens a side channel.
  4. LANGSEC in cryptographic contexts: Figuring out which protocol you’re speaking is the third hard problem in computer science.

Let’s get to it!

Trusted hardware isn’t so trustworthy

Fundamental non-cryptographic vulnerabilities in trusted hardware are nothing new. Years of vulnerabilities have led to Intel’s decision to remove SGX from its next generation of consumer CPUs, and ROCA affected one in four TPMs back in 2017.

What is new is the prevalence of trusted hardware in consumer-facing roles. Ordinary users are increasingly (and unwittingly!) interacting with secure enclaves and TEEs via password managers and 2FA schemes like WebAuthn on their mobile phones and computers. This has fundamentally broadened the risk associated with vulnerabilities in trusted hardware: breaks in trusted hardware now pose a direct risk to individual users.

That’s where our first highlight from RWC 2022 comes in: “Trust Dies in Darkness: Shedding Light on Samsung’s TrustZone Cryptographic Design” (slides, video, paper). In this session, the presenters describe two critical weaknesses in TEEGRIS, Samsung’s implementation of a TrustZone OS: an IV reuse attack that allows an attacker to extract hardware-protected keys, and a downgrade attack that renders even the latest and patched flagship Samsung devices vulnerable to the first attack. We’ll take a look at both.

IV reuse in TEEGRIS

TEEGRIS is an entirely separate OS, running in isolation and in parallel with the “normal” host OS (Android). To communicate with the host, TEEGRIS provides a trusted application (TA) that runs within the TEE but exposes resources to the normal host via Keymaster, a command-and-response protocol standardized by Google.

Keymaster includes the concept of “blobs”: encryption keys that have themselves been encrypted (“wrapped”) with the TEE’s key material and stored on the host OS. Because the wrapped keys are stored on the host, their security ultimately depends on the security of the TEE’s correct application of encryption during key wrapping.

So how does the TEEGRIS Keymaster wrap keys? With AES-GCM!

As you’ll recall, there are (normally) three parameters for a block cipher (AES) combined with a mode of operation (GCM):

  • The secret key, used to initialize the block cipher
  • The initialization vector (IV), used to perturb the ciphertext and prevent our friend the ECB penguin
  • The plaintext itself, which we intend to encrypt (in this case, another encryption key)

The security of AES-GCM depends on the assumption that an IV is never reused for the same secret key. Therefore, an attacker that can force the secret key and IV to be used across multiple “sessions” (in this case, key wrappings) can violate the security of AES-GCM. The presenters discovered mistakes in Samsung’s Keymaster implementation that violate two security assumptions: that the key derivation function (KDF) can’t be manipulated to produce the same key multiple times, and that the attacker can’t control the IV. Here’s how:

  • On the Galaxy S8 and S9, the KDF used to generate the secret key used only attacker-controlled inputs. In other words, an attacker can force all encrypted blobs for a given Android application to use the exact same AES key. In this context, this is acceptable as long as an attacker cannot force IV reuse, except
  • …the Android application can set an IV when generating or importing a key! Samsung’s Keymaster implementation on the Galaxy S9 trusts the IV passed in by the host, allowing an attacker to use the same IV multiple times.

At this point, the properties of the stream cipher itself give the attacker everything they need to recover an encryption key from another blob: the XOR of the malicious blob, the malicious key, and the target (victim) blob that yields the plaintext of the target, which is the unwrapped encryption key!

Ultimately, the presenters determined that this particular attack worked only on the Galaxy S9: the S8’s Keymaster TA generates secret keys from attacker-controlled inputs but doesn’t use an attacker-provided IV, preventing IV reuse.

The talk’s presenters reported this bug in March of 2021, and it was assigned CVE-2021-25444.

Downgrade attacks

As part of their analysis of Samsung’s TrustZone implementation, the presenters discovered that the Keymaster TA on Galaxy S10, S20, and S21 devices used a newer blob format (“v20-s10”) by default. This new format changes the data used to seed the KDF: instead of being entirely attacker controlled, random bytes (derived from the TEE itself) are mixed in, preventing key reuse.

But not so fast: the TEE on the S10, S20, and S21 uses the “v20-s10” format by default but allows the application to specify a different blob version to use instead. The version without any randomized salt (“v15”) is one of the valid options, so we’re right back where we started with predictable key generation.

The talk’s presenters reported this bug in July of 2021, and it was assigned CVE-2021-25490.

Takeaways

TEEs are not special: they’re subject to the same cryptographic engineering requirements as everything else. Hardware guarantees are only as good as the software running on top of them, which should (1) use modern ciphers with misuse-resistant modes of operation, (2) minimize potential attacker influence over key and key derivation material, and (3) eliminate the attacker’s ability to downgrade formats and protocols that should be completely opaque to the host OS.

Security tooling is still too difficult to use

We at Trail of Bits are big fans of automated security tooling: it’s why we write and open-source tools like dylint, pip-audit, siderophile, and Echidna.

That’s why we were saddened by the survey results in “‘They’re not that hard to mitigate’: What Cryptographic Library Developers Think About Timing Attacks” (slides, video, paper): of 44 cryptographers surveyed across 27 major open-source cryptography projects, only 17 had actually used automated tools to find timing vulnerabilities, even though 100% of the participants surveyed were aware of timing vulnerabilities and their potential severity. The following are some of the reasons participants cited for choosing not to use automated tooling:

  • Skepticism about risk: Many participants expressed doubt that they needed additional tooling to help mitigate timing attacks or that there were practical real-world attacks that justified the effort required for mitigation.
  • Difficulty of installation or use: Many of the tools surveyed had convoluted installation, compilation, and usage instructions. Open-source maintainers expressed frustration when trying to make projects with outdated dependencies work on modern systems, particularly in contexts in which they’d be most useful (automated testing in CI/CD).
  • Maintenance status: Many of the tools surveyed are source artifacts from academic works and are either unmaintained or very loosely maintained. Others had no easily discoverable source artifacts, had binary releases only, or were commercially or otherwise restrictively licensed.
  • Invasiveness: Many of the tools introduce additional requirements on the programs they analyze, such as particular build structures (or program representations, such as C/C++ or certain binary formats only) and special DSLs for indicating secret and public values. This makes many tools inapplicable to newer projects written in languages like Python, Rust, and Go.
  • Overhead: Many of the tools involve significant learning curves that would take up too much of a developer’s already limited time. Many also require a significant amount of time to use, even after mastering them, in terms of manually reviewing and eliminating false positives and negatives, tuning the tools to increase the true positive rate, and so forth.

Perhaps unintuitively, awareness of tools did not correlate with their use: the majority of developers surveyed (33/44) were aware of one or more tools, but only half of that number actually chose to use them.

Takeaways

In the presenters’ words, there is a clear “leaky pipeline” from awareness of timing vulnerabilities (nearly universal), to tool awareness (the majority of developers), to actual tool use (a small minority of developers). Stopping those leaks will require tools to become:

  • Easier to install and use: This will reduce the cognitive overhead necessary between selecting a tool and actually being able to apply it.
  • Readily available: Tools must be discoverable without requiring intense familiarity with active cryptographic research; tools should be downloadable from well-known sources (such as public Git hosts).

Additionally, the presenters identified compilers themselves as an important new frontier: the compiler is always present, is already familiar to developers, and is the ideal place to introduce more advanced techniques like secret typing. We at Trail of Bits happen to agree!

Side channels everywhere

The great thing about side-channel vulnerabilities is their incredible pervasiveness: there’s a seemingly never-ending reservoir of increasingly creative techniques for extracting information from a target machine.

Side channels are typically described along two dimensions: passive-active (i.e., does the attacker need to interact with the target, and to what extent?) and local-remote (i.e., does the attacker need to be in the physical vicinity of the target?). Remote, passive side channels are thus the “best of both worlds” from an attacker’s perspective: they’re entirely covert and require no physical presence, making them (in principle) undetectable by the victim.

We loved the side channel described in “Lend Me Your Ear: Passive Remote Physical Side Channels on PCs” (video, paper). To summarize:

  • The presenters observed that, on laptops, the onboard microphone is physically wired to the audio interface (and, thus, to the CPU). Digital logic controls the intentional flow of data, but it’s all just wires and, therefore, unintentional noise underneath.
  • In effect, this means that the onboard microphone might act as an EM probe for the CPU itself!
  • We share our audio over the internet to potentially untrusted parties: company meetings, conferences, VoIP with friends and family, voice chat for video games, and so on…
  • …so can we extract anything of interest from that data?

The presenters offered three case studies:

  • Website identification: A victim is browsing a website while talking over VoIP, and the attacker (who is on the call with the victim) would like to know which site the victim is currently on.
    • Result: Using a convolutional neural network with a 14-way classifier (for 14 popular news websites), the presenters were able to achieve 96% accuracy.
  • Cryptographic key recovery: A victim is performing ECDSA signatures on her local machine while talking over VoIP, and the attacker would like to exfiltrate the secret key being used for signing.
    • Result: The presenters were able to use the same side-channel weakness as Minerva but without local instrumentation. Even with post-processing noise, they demonstrated key extraction after roughly 20,000 signing operations.
  • CS:GO wallhacks: A victim is playing an online first-person shooter while talking with other players over VoIP, and the attacker would like to know where the victim is physically located on the game map.
    • Result: Distinct “zebra patterns” were visually identifiable in the spectrogram when the victim was hidden behind an opaque in-game object, such as a car. The presenters observed that this circumvented standard “anticheat” mitigations, as no client code was manipulated to reveal the victim’s in-game location.

Takeaways

Side channels are the gift that keeps on giving: they’re difficult to anticipate and to mitigate, and they compromise cryptographic schemes that are completely sound in the abstract.

The presenters correctly note that this particular attack upends a traditional assumption about physical side channels: that they cannot be exploited remotely and, thus, can be excluded from threat models in which the attacker is purely remote.

LANGSEC in cryptographic contexts

LANGSEC is the “language-theoretic approach to security”: it attributes many (most?) exploitable software bugs to the ad hoc interpretation of potentially untrusted inputs and proposes that we parse untrusted inputs by comparing them against a formal language derived solely from valid or expected inputs.

This approach is extremely relevant to the kinds of bugs that regularly rear their heads in applied cryptography:

We saw not one, but two LANGSEC-adjacent talks at RWC this year!

Application layer protocol confusion

The presenters of “ALPACA: Application Layer Protocol Confusion—Analyzing and Mitigating Cracks in TLS Authentication” (slides, video, paper) started with their observation of a design decision in TLS: because TLS is fundamentally application and protocol independent, it has no direct notion of how the two endpoints should be communicating. In other words, TLS cares only about establishing an encrypted channel between two machines, not (necessarily) which machines or which services on those machines are actually communicating.

In their use on the web, TLS certificates are normally bound to domains, preventing an attacker from redirecting traffic intended for safe.com to malicious.biz. But this isn’t always sufficient:

  • Wildcard certificates are common: an attacker who controls malicious.example.com might be able to redirect traffic from safe.example.com if that traffic were encrypted with a certificate permitting *.example.com.
  • Certificates can claim many hosts, including hosts that have been obtained or compromised by a malicious attacker: the certificate for safe.example.com might also permit safe.example.net, which an attacker might control.
  • Finally, and perhaps most interestingly, certificates do not specify which service and/or port they expect to authenticate with, creating an opportunity for an attacker to redirect traffic to a different service on the same host.

To make this easier for the attacker, hosts frequently run multiple services with protocols that roughly resemble HTTP. The presenters evaluated four of them (FTP, SMTP, IMAP, and POP3) against three different attack techniques:

  • Reflection: A MiTM attacker redirects a cross-origin HTTPS request to a different service on the same host, causing that service to “reflect” a trusted response back to the victim.
  • Download: An attacker stores malicious data on a service running the same host and tricks a subsequent HTTPS request into downloading and presenting that data, similarly to a stored XSS attack.
  • Upload: An attacker compromises a service running on the same host and redirects a subsequent HTTPS request to the service, causing sensitive contents (such as cookie headers) to be uploaded to the service for later retrieval.

Next, the presenters evaluated popular web browsers and application servers for FTP, SMTP, IMAP, and POP3 and determined that:

  • All browsers were vulnerable to at least two attack techniques (FTP upload + FTP download) against one or more FTP server packages.
  • Internet Explorer and Microsoft Edge were particularly vulnerable: all exploit methods worked with one or more server packages.

This is all terrible great, but how many actual servers are vulnerable? As it turns out, quite a few: of 2 million unique hosts running a TLS-enabled application server (like FTP or SMTP), over 1.4 million (or 69%) were also running HTTPS, making them potentially vulnerable to a general cross-protocol attack. The presenters further narrowed this down to hosts with application servers that were known to be exploitable (such as old versions of ProFTPD) and identified over 114,000 HTTPS hosts that could be attacked.

So what can we do about it? The presenters have some ideas:

  • At the application server level, there are some reasonable countermeasures we could apply: protocols like FTP should be more strict about what they accept (e.g., refusing to accept requests that look like HTTP) and should be more aggressive about terminating requests that don’t resemble valid FTP sessions.
  • At the certificate level, organizations should be wary of wildcard and multi-domain certificates and should avoid shared hosts for TLS-enabled applications.
  • Finally, at the protocol level, TLS extensions like ALPN allow clients to specify the application-level protocol they expect to communicate with, potentially allowing the target application server (like SMTP) to reject the redirected connection. This requires application servers not to ignore ALPN, which they frequently do.

Takeaways

  • Despite being known and well understood for years, cross-protocol attacks are still possible today! Even worse, trivial scans reveal hundreds of thousands of exploitable application servers running on shared HTTPS, making the bar for exploitation very low.
  • This space is not fully explored: application protocols like SMTP and FTP are obvious targets because of their similarity to HTTP, but newer protocols are also showing up in internet services such as VPN protocols and DTLS.

“Secure in isolation, vulnerable when composed”: ElGamal in OpenPGP

The presenters of “On the (in)security of ElGamal in OpenPGP” (slides, video, paper) covered another LANGSEC-adjacent problem: standards or protocols that are secure in isolation but insecure when interoperating.

The presenters considered ElGamal in implementations of OpenPGP (RFC 4880) due to its (ahem) unique status among asymmetric schemes required by OpenPGP:

  • Unlike RSA (PKCS#1) and ECDH (RFC 6637), ElGamal has no formal or official specification!
  • The two “official” references for ElGamal are the original paper itself and the 1997 edition of the Handbook of Applied Cryptography, which disagree on parameter selection techniques! The OpenPGP RFC cites both; the presenters concluded that the RFC intends for the original paper to be authoritative.

(By the way, did you know that this is still a common problem for cryptographic protocols, including zero-knowledge, MPC, and threshold schemes? If that sounds scary (it is) and like something you’d like to avoid (it is), you should check out ZKDocs! We’ve done the hard work of understanding best practices for protocol and scheme design in the zero-knowledge ecosystem so that you don’t have to.)

The presenters evaluated three implementations of PGP that support ElGamal key generation (GnuPG, Botan, and libcrypto++) and found that none obey RFC 4880 with regard to parameter selection: all three use different approaches to prime generation.

But that’s merely the beginning: many OpenPGP implementations are proprietary or subject to long-term changes, making it difficult to evaluate real-world deviation from the standard just from open-source codebases. To get a sense for the real world, the presenters surveyed over 800,000 real-world ElGamal keys and found that:

  • The majority of keys appear to be generated using a “safe primes” technique.
  • A large minority appear to be using Lim-Lee primes.
  • A much smaller minority appear to be using Schnorr or similar primes.
  • Just 5% appear to be using “quasi-safe” primes, likely indicating an intent to be compliant with RFC 4880’s prime generation requirements.

Each of these prime generation techniques is (probably) secure in isolation…but not when composed: each of Go, GnuPG, and libcrypto++’s implementations of encryption against an ElGamal public key were vulnerable to side-channel attacks enabling plaintext recovery because of the unexpected prime generation techniques used for ElGamal keys in the wild.

The bottom line: of the roughly 800,000 keys surveyed, approximately 2,000 were vulnerable to practical plaintext recovery because of the “short exponent” optimization used to generate them. To verify the feasibility of their attack, the presenters successfully recovered an encrypted message’s plaintext after about 2.5 hours of side-channel analysis of GPG performing encryptions.

Takeaways

  • ElGamal is an old, well-understood cryptosystem, one whose parameters and security properties are straightforward on paper (much like RSA) but is subject to significant ambiguity and diversity in real-world implementations. Standards matter for security, and ElGamal needs a real one!
  • Cryptosystem security is pernicious: it’s not enough to be aware of potential side channels via your own inputs; signing and encryption schemes must also be resistant to poorly (or even just unusually) generated keys, certificates, etc.

Honorable mentions

There were a lot of really great talks at this year’s RWC—too many to highlight in a single blog post. Some others that we really liked include:

  • “Zero-Knowledge Middleboxes” (slides, video, paper): Companies currently rely on TLS middleboxes (and other network management techniques, like DNS filtering) to enforce corporate data and security policies. Middleboxes are powerful tools, ones that are subject to privacy abuses (and subsequent user circumvention by savvy users, undermining their efficacy). This talk offers an interesting (albeit still experimental) solution: use a middlebox to verify a zero-knowledge proof of policy compliance, without actually decrypting (and, therefore, compromising) any TLS sessions! The key result of this solution is compliance with a DNS policy without compromising a user’s DNS-over-TLS session, with an overhead of approximately five milliseconds per verification (corresponding to one DNS lookup).
  • “Commit Acts of Steganography Before It’s Too Late” (slides, video): Steganography is the ugly duckling of the cryptographic/cryptanalytic world, with research on steganography and steganalysis having largely dried up. Kaptchuk argues that this decline in interest is unwarranted and that steganography will play an important role in deniable communication with and within repressive states. To this end, the talk proposes Meteor, a cryptographically secure steganographic scheme that uses a generative language model to hide messages within plausible-looking human-language sentences.

See you in 2023!

Improving the state of go-fuzz

By Christian Presa Schnell

During my winternship, I used the findings from recent Go audits to make several improvements to go-fuzz, a coverage-based fuzzer for projects written in Go. I focused on three enhancements to improve the effectiveness of Go fuzzing campaigns and provide a better experience for users. I contributed to fixing type alias issues, integrating dictionary support, and developing new mutation strategies.

What is go-fuzz?

go-fuzz finds software bugs by providing random input to a program and monitoring it for errors. It consists of two main components: go-fuzz and go-fuzz-build. The go-fuzz-build component is responsible for the source code instrumentation. And once the source code of the target program is instrumented, the code is compiled and the binary is then used by go-fuzz for the fuzzing campaign.

A user first instruments the source code to the tool, allowing for information, such as the coverage at runtime, to be extracted. Then, go-fuzz executes the program with a given set of inputs that are mutated with each interaction as it tries to increase coverage and trigger unexpected behaviors that lead to crashes. The harness, also provided by the user, is the fuzzing entry point and calls the function to be fuzzed. It returns a value to go-fuzz indicating whether the input should be dropped or promoted within the input corpus.

go-fuzz has been very successful in discovering new bugs, and the tool has helped find more than 200 bugs that are highlighted on GitHub and many more during Trail of Bits audits.

Instrumentation with type aliases

My first task was to investigate the root cause of a bug that crashed go-fuzz and propose a fix for it. In particular, the crash error we obtained was undefined: fs in fs.FileMode. A more detailed description of the bug can be found in issue dvyukov/go-fuzz#325.

This bug occurs only with Go version 1.16 and higher and when interacting with the file system via the os package rather than with fs. As many projects interact with the file system, this issue is of great importance, and therefore, the improvements I proposed are essential to increasing go-fuzz’s usability.

Even though there’s a workaround for this bug, it is still necessary to modify the code by adding statements using the fs package. This is not an ideal solution, since it requires one to manually modify the code, which may influence the fuzzing harness.

Another way of solving the problem is to simply use Go version 1.15. However, this is also problematic, since it is not always possible to run the project that we want to fuzz with a lower version of Go. Therefore, we wanted to find a thorough solution that would not require these constraints.

The error didn’t point to the root cause of the crash, so we needed to perform a detailed analysis.

Bug reproduction

I developed a minimal program that crashes go-fuzz-build based on the GitHub issue. The function that caused the bug, which is called HomeDir below, gets the stats for a file and checks whether the permission for the file and the current user is writable.

package homedir
​
import (
	"os"
	"fmt"
)
​
​
func HomeDir() {
	p := "text.txt"
	info, _ := os.Stat(p)
​
	if info.Mode().Perm()&(1<<(uint(7))) & 1 != 0 {
		fmt.Println("test")
	}
}

To successfully instrument the program with go-fuzz-build, we needed to provide a fuzzing harness. Since we simply wanted to instrument the program, the harness did not require the HomeDir function to be invoked. So I implemented the harness in another file but in the same package as the HomeDir function so that the function could be instrumented without being called, allowing us to investigate the issue.

package homedir

func Fuzz(data []byte) int {
	return 1
}

After looking at this code, the cause of the go-fuzz-build crash seemed even more confusing. The crash was related to the fs package, but the fs package was not used in the program:

failed to execute go build: exit status 2
homedir.go:13: undefined: fs in fs.FileMode

Bug triage

Interestingly, this bug was not introduced by a particular commit to go-fuzz, but it appeared when go-fuzz was used with a Go version of 1.16 and higher, which means that some change from Go version 1.15 to 1.16 had to be the reason for this issue.
​​
Since the crash occurred when compiling the instrumented source code, figuring out where go-fuzz-build crashed was easy. The instrumentation was somehow faulty and produced non-valid code.

//line homedir.go:1
package homedir
​
//line homedir.go:1
import (
//line homedir.go:1
	_go_fuzz_dep_ "go-fuzz-dep"
//line homedir.go:1
)
​
import (
	"os"
	"fmt"
)
​
//line homedir.go:8
func HomeDir() {
//line homedir.go:8
	_go_fuzz_dep_.CoverTab[20570]++
	p := "text.txt"
	info, _ := os.Stat(p)
​
//line homedir.go:13
	if func() _go_fuzz_dep_.Bool {
//line homedir.go:13
		__gofuzz_v1 := fs.FileMode(info.Mode().Perm() & (1 << 7))
//line homedir.go:13
		_go_fuzz_dep_.Sonar(__gofuzz_v1, 0, 725889)
//line homedir.go:13
		return __gofuzz_v1 != 0
//line homedir.go:14
	}() == true {
//line homedir.go:14
		_go_fuzz_dep_.CoverTab[5104]++
		fmt.Println("test")
	} else {
//line homedir.go:14
		_go_fuzz_dep_.CoverTab[24525]++
//line homedir.go:14
	}
​
//line homedir.go:14
}
​
//line homedir.go:15
var _ = _go_fuzz_dep_.CoverTab

Root cause analysis

The expression in line 13 of the original program, (info.Mode().Perm() & (1 << 7)), is explicitly converted to the fs.FileMode type. This type conversion is one of the modifications performed by the instrumentation. The type conversion is correct by itself, since the info.Mode().Perm() has the type fs.FileMode. The real problem is that while the fs package is used, there lacks an import for it. Therefore, the compiler cannot resolve the type conversion, and the compilation fails.

However, this does not answer the question of why go-fuzz-build crashes in Go version 1.16 and up and not in lower versions. We found the answer to this question by looking at the differences between 1.15 and 1.16: the FileMode type in the os package changed from type FileMode uint32 in Go 1.15 to type FileMode = fs.FileMode in Go 1.16.

Essentially, the FileMode type changed from a type definition with the underlying uint32 type to a type alias with a type target defined in the fs package. A type alias does not create a new type. Instead, it just defines a new name for the original type. For this reason, the typechecker used by go-fuzz-build identifies fs.FileMode as the type that should be used for the type conversion instead of the type alias defined in the os package. This should not be an issue if the type alias and the original type are in the same package, but if there are multiple packages, the corresponding import statements should be added to the instrumented code.

Proposed fix

Ideally, a fix for this issue should be future-proof. While it is possible to hard-code the case of the fs.FileMode, this is not sufficient since other type aliases might be introduced in future versions of Go or in external packages used by the fuzzed code, so more fixes would be required. My proposed fix addresses this problem.

The fix I proposed consists of the following steps. First, analyze the typechecker output for every instrumented file for types that are defined in non-imported packages. If such a type exists, an import statement will be added with the corresponding package. However, there might be cases in which such a type exists but the instrumentation does not use it to perform a type conversion. That would render the import statement that was added to an unused import, and consequently, the compiler would refuse to compile the code. Therefore, it is essential to remove the unused added imports. For that purpose, goimports, a program that optimizes imports, will be executed before compilation. Then, the compilation succeeds.

Because the initializer is imported by the package in which the alias is defined, the package is guaranteed to execute only once. Therefore, we don’t have to worry about the import statement changing the semantics of the source code.

Dictionary support

​The mutation engines of general-purpose fuzzers are designed to be very effective when mutating binary data formats, such as images or compressed data. However, general-purpose fuzzers don't perform very well when mutating inputs for syntax-aware programs, as they will accept only inputs that are valid for the underlying grammar. Common examples for such targets are programs that parse human-readable data formats like languages (SQL) or text-based protocols (HTTP, FTP).

Most of the time, in order to achieve good results with such human-readable targets, you have to build a custom mutation engine that adheres to the syntax, which is complex and time-consuming.

Another approach is to use fuzzing dictionaries. Fuzzing dictionaries are a collection of interesting keywords that are relevant for the required syntax. This approach allows a general-purpose mutation engine to insert keywords into the input at random positions. This gives the fuzzer more valid inputs than it would get with mutations on the bytes.

Up to this point, go-fuzz’s mutation engine generated a list of keywords using a technique called “token capture” and inserted these keywords into the mutated inputs. This technique extracts interesting strings directly from the instrumented code by looking for hard-coded values. The reasoning behind this approach is that if the input requires a certain syntax, there would be hard-coded statements within the program that check the validity of the input. While token capturing is correct, it has an important drawback: not only are the relevant keywords extracted, but so are keywords that are irrelevant to the input, such as log message strings. This is problematic, since adding noise to the string list reduces the fuzzer’s overall effectiveness.

A different approach is to let the user provide dictionaries containing interesting keywords relevant for the specific syntax used by the targeted program. I proposed a modification that allows one to pass a -dict parameter to go-fuzz and to provide a dictionary file containing the keywords (in the AFL/libFuzzer format) and a level parameter to provide more fine-grained control over the tokens in the dictionary file.

The following example illustrates the syntax of a token dictionary for SQL:

false]
function_abs=" abs(1)"
function_avg=" avg(1)"
function_changes=" changes()"
function_char=" char(1)"
function_coalesce=" coalesce(1,1)"
function_count=" count(1)"
function_date=" date(1,1,1)"
(...)
keyword_ADD="ADD"
keyword_AFTER="AFTER"
keyword_ALL="ALL"
keyword_ALTER="ALTER"
keyword_ANALYZE="ANALYZE"
keyword_AND="AND"
(...)

By adopting the same syntax for the dictionaries used by AFL and libFuzzer, we can reuse preexisting dictionaries containing important keywords for specific fuzzing targets without having to redefine the keywords in a new format.

New mutation strategies

A fuzzer’s effectiveness depends on the quality of its mutation algorithms and whether they lead to more diverse inputs and increased code coverage. To this effect, I developed three new mutation strategies for go-fuzz.

Insert repeated bytes
This strategy mutates the fuzzer’s previous input by inserting a random byte that is repeated a random number of times. This is a variation of the insert random bytes strategy from libFuzzer that increases the likelihood of a situation in which certain bytes are repeated.

Shuffle bytes
Another mutation strategy inspired by libFuzzer, shuffle bytes selects a random subpart of the input with a random length and shuffles it using the Fisher-Yates shuffling algorithm.

Little endian base 128
Last but not least, I improved the InsertLiteral mutation strategy by implementing the little endian base 128 (LEB128) encoding. Similar to the process of inserting string literals discussed in the section on dictionaries above, with this improved strategy, the mutation engine scans the source code for hard-coded integer values and inserts them into the input to mutate it.

Inserting strings into the input is straightforward, as strings have a direct byte representation. This is not the case for integer values, since there are multiple formats to store the values in bytes depending on the length of the integer (8, 16, 32, and 64 bits) and on the endianness on which the integer is stored, either little endian or big endian. For this reason, the mutation engine needs to be able to insert the integer literals in different formats, since they might be used by the fuzzed program.

LEB128 is a variable-length encoding algorithm that is able to store integers by using very few bytes. In particular, LEB128 can store small integer values without leading zero bytes as well as arbitrarily big integers. Additionally, there are two different variants of the LEB128 encoding that have to be implemented separately: unsigned LEB128 and signed LEB128.

Because of its efficiency, this encoding is very popular and is used in many projects, like LLVM, DWARF, and Android DEX. Therefore, go-fuzz’s support of it is very useful.

The future of go-fuzz

The recent release of Go version 1.18 introduced first-party support for fuzzing. Hence, go-fuzz has reached the end of its life and future improvements will most likely be limited to bug fixes. Nonetheless, enhancing go-fuzz is still useful, as it is a well-known solution with an ecosystem of helpful tools, like trailofbits/go-fuzz-utils, and it may still be used in older projects.

I hope that the proposed improvements will be adopted upstream into go-fuzz so that everyone can benefit from them to discover and fix new bugs. Even though Go’s new built-in fuzzer will gain popularity due to its ease of use, we hope that Go developers will continue to draw inspiration from go-fuzz, which has been a huge success so far. It will certainly be interesting to see what the future holds for the fuzzing of Go projects.

I am very grateful for the opportunity to have worked as an intern at Trail of Bits and on the go-fuzz project—it was a great learning experience. I would like to thank my mentors, Dominik Czarnota and Rory Mackie, for their guidance and support.