XKEYSCORE, Cipher Detection, and You!

Open PDF +1 other copy
Creating agency: NSA National Security Agency (US)
Document date: 2008-08-21
Pages: 17
Genre: slides
Banner:
Classification: TOP SECRET COMINT
Dissemination: REL TO USA, FVEY

A TOP SECRET presentation from NSA's Mathematics Research Group dated 21 August 2008, explaining how XKeyscore detects encrypted and steganographic communications — describing the fingerprint and C++ plug-in systems used to flag sessions using particular ciphers, VPNs, encrypted archives and hidden-data tools, with worked examples detecting RAR archives, OpenVPN, digital certificates and various encryption products, plus a revealing note that detection of encryption is itself used to identify communications worth targeting.

Long Description:
This is a TOP SECRET//COMINT//REL TO USA, FVEY presentation authored by NSA's Mathematics Research Group, dated 21 August 2008. The presentation focuses specifically on using XKeyscore to detect cipher use, encryption and steganography — a complement to the analyst and developer training documents that focus on traffic classification and querying. The presentation situates XKeyscore within the collection architecture. Data sources feeding the system include FORNSAT (satellite downlink), Overhead (uplink), Special Source, Tailored Access, F6 (Special Collection Service), FISA (described as limited) and third party. Front-end processing by WEALTHYCLUSTER2/TURMOIL demodulates, demultiplexes, packetizes and sessionizes the traffic, with a "Decrypt?" step noted. XKeyscore then selects tasked CADENCE/UTT terms, sends hits to PINWALE/PRESSUREWAVE, tips to TRAFFICTHIEF, performs fingerprinting and supports SIGINT development through two rolling buffers — metadata (approximately 30 days, searchable in a MySQL database) and content (approximately 7 days, retrievable from disk archive). This document gives specific buffer figures: ~30 days metadata, ~7 days content, somewhat longer than the 3-5 day content figure in other documents, reflecting site variation. The fingerprinting system is described in technical detail. Fingerprints are pattern matches that mark a session as metadata without sending it to PINWALE — the analyst must search for the fingerprint to retrieve flagged sessions. Strings require a minimum of three fixed-byte anchors (with an exception for two bytes at the start of a session), regular expressions must contain a non-optional three-byte string, and context-dependent terms are supported, with XKeyscore reserving the right to increase the minimum to four bytes. The worked examples reveal specific encryption detection fingerprints: encryption/helixstronghold matching a Helix Stronghold encrypted file header, encryption/wharfrat matching specific byte sequences on ports 443 or 80, encryption/the_algorithm using a regex, encryption/kryptel matching a hex signature, encryption/cipherpad matching a CPAD1 marker within the first 4000 bytes, and certificate/digital_id matching certificate headers. VPN detection examples include vpn/openvpn/x509/wera matching OpenVPN over UDP. The syntax features section documents the fingerprint language's case sensitivity, full Boolean logic with parenthetical grouping, variables, and available functions including port, first, hex, pos, distance, lpos, last, follows, between and order. Fingerprint definitions are updated hourly across the entire enterprise. The plug-in section describes using the full power of C++ when pattern matching is insufficient, typically limited to certain file types due to volume (huge JPEG volume from web surfing is noted). Named steganography and encryption plug-ins include PHOSPHORESSENCE (a library of steganography detectors), SHELLLOCK (steganography detection) and SEDENA (indigenous/foreign encryption software detection). The drawback noted is that plug-ins require a site upgrade to deploy. The compromise solution — snippets of C++ code embedded in fingerprints, deployed hourly with most of the flexibility of a full plug-in — is shown detecting RAR encrypted archives by checking specific byte flags, and an anchorless regex follow-on check for DHCP client-to-server traffic. The releasability section contains significant compartment disclosures. Nearly all XKeyscore personnel hold PICARESQUE, with those lacking it holding PRIVAC. XKeyscore distribution comes in two flavours — first and second party, and third party — with no NOFORN capabilities permitted in the shared versions. Special dispensation was granted for some capabilities to SMOKYSINK. PICARESQUE code could be kept running on R1's rednet if absolutely necessary. PICARESQUE is the same ECI compartment named in the BULLRUN briefing as one of the three named exceptionally controlled compartments protecting NSA's cryptanalytic capabilities, confirming that XKeyscore's encryption-detection and exploitation functions were protected under the same compartment that shielded NSA's broader anti-encryption programme. The document notes that all data are stored, not just hits, and that a session with detected encryption is marked but not sent to PINWALE. The integration of mathematical/cryptanalytic research into XKeyscore's fingerprinting, the named steganography detection libraries, and the PICARESQUE compartment linkage together show that XKeyscore was not merely a traffic-collection and classification system but an active front-line tool in NSA's effort to identify and defeat encrypted communications.
Programs:
XKEYSCORE, WEALTHYCLUSTER, TURMOIL, CADENCE, UTT, PINWALE, PRESSUREWAVE, TRAFFICTHIEF, PHOSPHORESSENCE, SHELLLOCK, SEDENA, SMOKYSINK, PICARESQUE, PRIVAC, WHARFRAT

People mentioned:
-

Countries:
-

Tags:
Mathematics Research Group, cipher detection, encryption detection, steganography, fingerprints, FORNSAT, F6, FISA, RAR, OpenVPN, x509, digital certificate, Kryptel, CipherPad, Helix Stronghold, VPN analysis, C++ plug-in, code-based fingerprint, rolling buffer, metadata, content buffer, retrospective retrieval, anchor, regex, DHCP, ECI, releasability, rednet

Identifier:
xks-cipher-detection-and-you
Also known as:
EFF_-_20131211-svt-xkeyscore_sources

PDF SHA-256:
56cd85589f3a9e3ca5d74d200a55015a15bdff8d603d7b76e83760fc50ad3b9d

TOP SECRET//COMINT//REL TO USA, FVEY

XKEYSCORE, Cipher Detection, and You!

[REDACTED]

Mathematics Research Group
21 August 2008

TOP SECRET//COMINT//REL TO USA, FVEY


UNCLASSIFIED

The Protocol Stack

  • Application Layer (HTTP, FTP, etc.)
  • Transport Layer (TCP, UDP)
  • Network Layer (IPv4, IPv6)
  • Data Link Layer (PPP)
  • Physical Layer (Copper, Fiber)

UNCLASSIFIED


TOP SECRET//COMINT//REL TO USA, FVEY

Data Sources

  • FORNSAT (downlink)
  • Overhead (uplink)
  • Special Source
  • Tailored Access
  • F6
  • FISA (limited)
  • 3rd party

TOP SECRET//COMINT//REL TO USA, FVEY


SECRET//COMINT//REL TO USA, FVEY

Front-end Processing

WEALTHYCLUSTER2/TURMOIL
Demodulate Demultiplex Packetize Sessionize
Decrypt?

SECRET//COMINT//REL TO USA, FVEY


SECRET//COMINT//REL TO USA, FVEY

What does XEYSCORE do?

  • Selection of tasked CADENCE/UTT terms.
  • Send hits to PINWALE/PRESSUREWAVE.
  • Tipping to TRAFFICTHIEF.
  • Fingerprinting.
  • SIGINT development using two rolling buffers:
    • Metadata
    • Content (data)

SECRET//COMINT//REL TO USA, FVEY


TOP SECRET//COMINT//REL TO USA, FVEY

Retrospective Searching

XKEYSCORE

  • All data are stored, not just hits.
  • Queries are distributed to entire network of sites.

Metadata Buffer

  • ~30 days
  • Searchable
  • MySQL database

Content Buffer

  • ~7 days
  • Retrievable
  • Archived on disk

TOP SECRET//COMINT//REL TO USA, FVEY


TOP SECRET//COMINT//REL TO USA, FVEY

Fingerprinting

  • Pattern matching against the data.
  • Session is marked, but not sent to PINWALE.
    • Fingerprint stored as metadata.
    • Have to search for it.
  • Rich set of patterns
    • Strings have a minimum of three* anchors (fixed bytes).
      • [Exception: Two bytes at the beginning of a session]
    • Regular expressions allowed (require nonoptional string of three* bytes within regex)
    • Context-dependent terms.
      • *XKS reserves the right to increase this to four.

TOP SECRET//COMINT//REL TO USA, FVEY


TOP SECRET//COMINT//REL TO USA, FVEY

Examples

7.0) = 'helix stronghold encrypted file';
'\xd6\x56\x34\xb7\x80\x05\xfe\x8b'c and
'\xaf\x52\x72\x60\xdd\xfe\x72\xc2'c and
(port(443) or port(80));
fingerprint('encryption/the_algorithm',
3.0)=
/-XYZ-.{0,30}mp[eg]/;

TOP SECRET//COMINT//REL TO USA, FVEY


TOP SECRET//COMINT//REL TO USA, FVEY

Syntax Features

  • Case Sensitivity
fingerprint('certificate/digital_id') =
'-BEGIN CERTIFICATE-'c;
  • Full Boolean logic
    • Grouping with parentheses
    • Operators: and, or, not
  • Variables
$udp = protocol('udp');
fingerprint('vpn/openvpn/x509/wera') =
$udp and 'openvpn_wera'c;

TOP SECRET//COMINT//REL TO USA, FVEY


TOP SECRET//COMINT//REL TO USA, FVEY

Available Functions

  • port
  • first
  • hex
fingerprint('encryption/kryptel') =
hex('E8E2454300040004635C4EE9A2F9D111A
489E498F70C0B43404F4BFA50F2D111A4898E6
30458E285');
  • pos
fingerprint('encryption/cipherpad') =
pos('CPAD1'c) < 4000;

TOP SECRET//COMINT//REL TO USA, FVEY


TOP SECRET//COMINT//REL TO USA, FVEY

  • Distance (similar to pos, but for distance between tokens)
  • Lpos
Spop_basic = lpos('+OK 'c) or '\nQUIT';
  • First
appid('mail/smtp/...) = first('ehlo') and ... ;
  • Last (similar to first)
  • Follows (one token after another)
  • Between (one token between two others)
  • Order

TOP SECRET//COMINT//REL TO USA, FVEY


TOP SECRET//COMINT//REL TO USA, FVEY

Other Features

  • Fingerprint definitions updated hourly throughout the entire enterprise.
  • Workflows
    • Submit through user interface.
    • Standing queries that run like cron jobs.
    • Limited follow-on processing.
  • User interface for fingerprint submission (coming soon).
    • Currently done by XKS personnel.

TOP SECRET//COMINT//REL TO USA, FVEY


TOP SECRET//COMINT//REL TO USA, FVEY

Plug-ins

  • Full power of C++ for when pattern matching does not suffice.
  • Usually limited to certain file types
    • Huge JPEG volume from web surfing
  • Current steg/encryption plugins that fingerprint sessions:
    • PHOSPHORESSENCE library of steg detectors
    • SHELLLOCK steg detection
    • SEDENA indigenous encryption software
  • Drawback: Must wait for site upgrade to deploy.

TOP SECRET//COMINT//REL TO USA, FVEY


TOP SECRET//COMINT//REL TO USA, FVEY

Trade-off

  • Fingerprints easily deployed, but limited to pattern matching.
  • Plug-ins slow to deploy, but allow for complex testing.
  • New compromise:
    • Snippets of C++ code in fingerprint
    • Deployed hourly like fingerprint with most of the flexibility of a full plug-in.
    • Very complicated tests probably still need to be plug-ins.
    • Currently stood up at only a few sites.

TOP SECRET//COMINT//REL TO USA, FVEY


TOP SECRET//COMINT//REL TO USA, FVEY

Example

fingerprint('encryption/archive/rar') =
       '\x52\x61\x72\x21\x1a\x07\x00'c
       : c++ {{
         const uint8_t *ptr =
           find_first("\x52\x61\x72\x21\x1a\x07\x00");
         if (ptr == NULL)
           return false;
         if (end()-ptr < 64)
           return false;
         if ((ptr[23] &0x04) != 0x04)
           return false;
         if ((ptr[10] &0x80) != 0x80)
           return false;
         return true;
       }};

TOP SECRET//COMINT//REL TO USA, FVEY


TOP SECRET//COMINT//REL TO USA, FVEY

Advanced Feature

  • Follow-on check with anchorless regexes:
%dhcp_check = regex {{
    ^[\x01\x02][\x01- ]\x06.*c\x82sc
  }};
appid('netmanagement/dhcp/client_to_server',
  3.0) =
        from_port(68) and to_port(67)
        : %dhcp_check;

TOP SECRET//COMINT//REL TO USA, FVEY


TOP SECRET//COMINT//REL TO USA, FVEY

Releasability Issues

  • Nearly all XKS personnel have PICARESQUE!
    • Those that don't have PRIVAC.
  • XKS distribution comes in two flavors
    • 1st & 2nd party
    • 3rd party
    • No NOFORN capabilities permitted.
    • Special dispensation from [REDACTED] for some capabilities to SMOKYSINK.
  • Can keep PICARESQUE code running on R1's rednet if absolutely necessary.

TOP SECRET//COMINT//REL TO USA, FVEY

Archive note: SVT Nyheter only published one slide ("Data Sources", slide 3) from this deck in December 2013.