Receiving RDS with the RTL-SDR

redsea is a command-line RDS decoder. I originally wrote it as a script to decode RDS from demultiplexed FM stereo sound. Later I've experimented with other ways to read the bits, and the latest addition is to support the RTL-SDR television receiver via the rtl_fm tool.

Redsea is on GitHub. It has minimal dependencies (perl core modules, C standard library, rtl-sdr command-line tools) and has been tested to work on OSX and Linux with good enough FM reception. All test results, ideas, and pull requests are welcome.

Update 12/2016: Redsea has seen a lot of development since this post was written; see Redsea 0.7, a lightweight RDS decoder.

What it says

The program prints out decoded RDS groups, one group per line. Each group will contain a PI code identifying the station plus varying other data, depending on the group type. The below picture explains the types of data you'll probably most often encounter.

A more verbose output can be enabled with the -l option (it contains the same information though). The -t option prefixes all groups with an ISO timestamp.

How it works

The DSP side of my program, named rtl_redsea, is written in C99. It's a synchronous DBPSK receiver that first bandpass filters ① the multiplex signal. A PLL locks onto the 19 kHz stereo pilot tone; its third harmonic (57 kHz) is used to regenerate the RDS subcarrier. Dividing it by 16 also gives us the 1187.5 Hz clock frequency. Phase offsets of these derived signals are adjusted separately.

The local 57 kHz carrier is synchronized so that the constellation lines up on the real axis, so we can work on the real part only ②. Biphase symbols are multiplied by the square-wave clock and integrated ③ over a clock period, and then dumped into a delta decoder ④, which outputs the binary data as bit strings into stdout ⑤.

Signal quality is estimated a couple of times per second by counting the number of "suspicious" integrated biphase symbols, i.e. symbols with halves of opposite signs. The symbols are being sampled with a 180° phase shift as well, and we can switch to that stream if it seems to produce better results.

This low-throughput binary string data is then handled by redsea.pl via a pipe. Synchronization and error detection/correction happens there, as well as decoding. Group data is then displayed on the terminal, in semi-human-readable form.

Future

My ultimate goal is to have a tool useful for FM DX, i.e. pretty good noise resistance.

Visualizing hex dumps with Unicode emoji

Memorizing SSH public key fingerprints can be difficult; they're just long random numbers displayed in base 16. There are some terminal-friendly solutions, like OpenSSH's randomart. But because I use a Unicode terminal, I like to map the individual bytes into characters in the Miscellaneous Symbols and Pictographs block.

This Perl script does just that:

@emoji = qw( 🌀  🌂  🌅  🌈  🌙  🌞  🌟  🌠  🌰  🌱  🌲  🌳  🌴  🌵  🌷  🌸
             🌹  🌺  🌻  🌼  🌽  🌾  🌿  🍀  🍁  🍂  🍃  🍄  🍅  🍆  🍇  🍈
             🍉  🍊  🍋  🍌  🍍  🍎  🍏  🍐  🍑  🍒  🍓  🍔  🍕  🍖  🍗  🍘
             🍜  🍝  🍞  🍟  🍠  🍡  🍢  🍣  🍤  🍥  🍦  🍧  🍨  🍩  🍪  🍫
             🍬  🍭  🍮  🍯  🍰  🍱  🍲  🍳  🍴  🍵  🍶  🍷  🍸  🍹  🍺  🍻
             🍼  🎀  🎁  🎂  🎃  🎄  🎅  🎈  🎉  🎊  🎋  🎌  🎍  🎎  🎏  🎒
             🎓  🎠  🎡  🎢  🎣  🎤  🎥  🎦  🎧  🎨  🎩  🎪  🎫  🎬  🎭  🎮
             🎯  🎰  🎱  🎲  🎳  🎴  🎵  🎷  🎸  🎹  🎺  🎻  🎽  🎾  🎿  🏀
             🏁  🏂  🏃  🏄  🏆  🏇  🏈  🏉  🏊  🐀  🐁  🐂  🐃  🐄  🐅  🐆
             🐇  🐈  🐉  🐊  🐋  🐌  🐍  🐎  🐏  🐐  🐑  🐒  🐓  🐔  🐕  🐖
             🐗  🐘  🐙  🐚  🐛  🐜  🐝  🐞  🐟  🐠  🐡  🐢  🐣  🐤  🐥  🐦
             🐧  🐨  🐩  🐪  🐫  🐬  🐭  🐮  🐯  🐰  🐱  🐲  🐳  🐴  🐵  🐶
             🐷  🐸  🐹  🐺  🐻  🐼  🐽  🐾  👀  👂  👃  👄  👅  👆  👇  👈
             👉  👊  👋  👌  👍  👎  👏  👐  👑  👒  👓  👔  👕  👖  👗  👘
             👙  👚  👛  👜  👝  👞  👟  👠  👡  👢  👣  👤  👥  👦  👧  👨
             👩  👪  👮  👯  👺  👻  👼  👽  👾  👿  💀  💁  💂  💃  💄  💅 );

while (<>) {
  if (/[a-f0-9:]+:[a-f0-9:]+/) {
    ($b, $m, $a) = ($`, $&, $');
    print $b.join("  ", map { $emoji[$_] } map hex, split /:/, $m)." ".$a;
  }
}

What's happening here? First we create a 256-element array containing a hand-picked collection of emoji. Naturally, they're all assigned an index from 0x00 to 0xff. Then we'll loop through standard input and look for lines containing colon-separated hex bytes. Each hex value is replaced with an emoji from the array.

Here's the output:

The script could easily be extended to support output from other hex-formatted sources as well, such as xxd:

Some additional methods for visualizing hex dumps and key fingerprints, from the comments section:

• PGP Strong Set Top 50 Fingerprint Art
• VizHash GD - a visual hash

Time-coding audio files

One day you'll need to include real-time UTC timestamps in audio. It's useful when reconstructing events from long, unsupervised surveillance microphone recordings, or when constantly monitoring and logging radio channels.

There's no standard method for doing this with WAV or FLAC files. One method would be to log the start time in the filename and calculate the time based on audio position. However, this is not possible with voice-activated or squelched recorders. It also relies on the accuracy and stability of the ADC clock.

I'll take a look at some ways to include an accurate timestamp directly in the in-band audio.

Least significant bit

Time information can be encoded in the least significant bit (LSB) of the 16-bit PCM samples. This "steganographic" method requires a lossless file format and lossless conversions. The script below truncates all samples of a raw single-channel signed-integer PCM stream to 15 bits and inserts a 20-byte ISO 8601 timestamp in ASCII roughly every second, preceded by a "mark" start bit. When played back, the LSB can be zeroed out to get rid of the timestamps. The WAV can also be played as such; the "ticking" sound will be practically inaudible at an amplitude of −96 dB. The outgoing PCM stream is then sent to SoX for WAV encoding.

#!/usr/bin/perl
use strict;
use warnings;
use DateTime;
 
my $snum    = 0;
my $writing = 0;
my $pos     = 0;
my $code    = "";
 
open my $out, '-|', 'sox -t .raw -e unsigned-integer -b 16 -r 44100 '.
                    '-c 1 - stamped.wav';
 
while (read STDIN, my $sample, 2) {
  $sample = unpack "s", $sample;
  my $bit = 0;
 
  if ($writing) {
    $bit = (ord(substr $code, $pos >> 3, 1) >> ($pos % 8)) & 1;
    if (++$pos >= length $code << 3) {
      $writing = 0;
      $bit     = 0;
    }
  } elsif ($snum++ % 44100 == 0) {
    $writing = 1;
    $pos     = 0;
    $bit     = 1;
    $code    = DateTime->now()->iso8601();
  }
 
  print $out pack "S", ($sample + 0x7FFF) & 0xFFFE | $bit;
  
}
close $out;

Note that the start bit of the timestamp will mark the moment the sample reached this script, and it could differ hundreds of milliseconds from the actual moment of reception at the microphone. Also, the timestamp does not mark the start of a second, but is rather timed by an arbitrary sample counter. One could also poll and write the timestamps in a continuous manner.

The above script could be modified to interface with my squelch script, by only inserting timestamps when squelch is not active. The resulting audio could then be efficiently encoded as FLAC.

lsb-time-read.pl reads back the timestamps, also printing the sample position of each. Below is a sound sample of a clean signal followed by a timestamped one.

Lossy-friendly approach

Lossy compression, by definition, does not retain the numeric values of samples, so they can't be treated as bit fields. Instead, we can use an analog modulation scheme like binary FSK. MP3 and Ogg Vorbis encoders will, at a reasonable bit rate, retain the structure of a sufficiently slow FSK burst. This method will work even if the timestamping phase is followed by an analog conversion.

Using the ultrasonic part of the spectrum comes to mind; but unfortunately such high frequencies are mainly ignored by a LPF at the encoder. However, we can use the higher end of the remaining spectrum and filter it out afterwards, if the recording consists of narrow-band speech. In the case of squelched conversation, we could write the timestamp only in the beginning of each transmission. This way it could even be in the speech frequencies.

fsk-timestamp.pl embeds the timestamps into PCM data; they can be read back using minimodem --rx --mark 11000 --space 13000 --file stamped.wav -q 1200.

A sound sample follows.

Descrambling the voice inversion scrambler

Voice inversion is a method of scrambling radio conversations to render speech nearly unintelligible in ordinary radio receivers. As the name implies, it inverts the audio spectrum of a signal, making the lowest frequencies the highest and vice versa. It is not considered encryption; it's merely a sort of Pig Latin on analogue signals. Several voice scramblers utilize it, like the Selectone ST-20.

Update 09/2017: I've later released a simple descrambler tool called deinvert. You should probably try that one instead; these old scripts will be preserved here though.

Voice inversion is cancelled by reapplying the inversion, i.e. inverting the audio spectrum again. Here I'll present some least-effort digital descrambling methods for the voice inversion scrambler that may be of interest to hobbyist listeners. The examples are written in Perl.

Easy

In a digitally sampled signal, whole-spectrum inversion can be achieved very easily in the time domain by multiplying every other sample by −1. This is equivalent to amplitude modulating a Nyquist frequency carrier with the signal; the upper sideband will get inverted and nicely overlaid with the lower because of symmetric folding.

Update 09/2017: I've later released a simple descrambler tool called deinvert. You should probably try that one instead; these old scripts will be preserved here though.

my $bandwidth = 4300;

my $fc = $bandwidth * 2;

# Using SoX for resampling and decoding/encoding WAV headers
open my $inf, '-|', 'sox scrambled.wav -r '.$fc.' -c 1 -t .s16 -';
open my $outf, '|-', 'sox -r '.$fc.' -c 1 -t .s16 - descrambled.wav';
my $sign = 1;

while (read $inf, my $sample, 2) {
  # Simply multiply every other sample by -1
  print $outf pack "s", (unpack "s", $sample) * $sign;
  $sign *= -1;
}

Because the whole spectrum is inverted, a sampling rate has to be chosen to (approximately) match the signal bandwidth. Slight distortion will still remain, unless the chosen Nyquist frequency perfectly matches the inverted zero frequency of the signal, or the "inversion carrier" as Selectone calls it. But speech will nevertheless be much more intelligible than in the original scrambled signal.

For example, consider a scrambled piece of audio that seems to have its highest frequency components at 4300 Hz. We would need to resample the audio at a rate of 8600 Hz and multiply every other sample by −1 to get intelligible audio.

To make things simpler, the Selectone ST-20B supports eight discrete carrier frequencies, namely 2632, 2718, 2868, 3023, 3196, 3339, 3495, and 3729 Hz, which they claim to be "the most commonly used inversion formats".

Difficult

If resampling is out of the question, we can also multiply the samples with a sine wave oscillating at the seemingly highest scrambled frequency. This will produce two sidebands; the lower will be our descrambled audio and will be conveniently at baseband. The upper sideband contains the inverted signal, but at such a high frequency it should not significantly impede intelligibility. We could improve the audio further by silencing the upper sideband using a lowpass filter.

# Sample rate
my $fs = 48000;

# Carrier frequency
my $fc = 3729;

# Optional filter - comment out to disable
my $filter = " sinc -$fc";

my $fc = freq($fc, $fs);

# Using SoX for resampling, filtering, encoding/decoding WAV headers
open my $in, '-|', 'sox scrambled.wav -c 1 -b 16 -e signed -t .raw -';
open my $out, '|-', 'sox -r '.$fs.' -c 1 -b 16 -e signed -t .raw - ' .
                    'descrambled.wav' . ($filter // "");

my $phase = 0;
while (read $in, my $sample, 2) {
  $phase += $fc;
  $phase -= 0x10000 if ($phase > 0x7FFF);

  # Multiply signal with sine wave
  print $out pack "s", (unpack "s", $sample) *
                       sin($phase / 0x7FFF * 3.14159);
}

sub freq {
  return int(.5 + $_[0] * 0x10000 / $_[1]);
}

A word about split-band scrambling

Some scramblers, like the PCD4440T, use a split-band inversion where the audio is split into two frequency bands that are then inverted separately and combined. The split frequency is user-adjustable. This is not a significant improvement; it would only require us to do the digital deinversion in two parts with different parameters.

Results

And here's a demo of what it sounds like. We begin with a (fake) scrambled message. Then the easy descramble comes on with a 1000 Hz error in the selected sampling rate; then the easy descramble with an error of 300 Hz; and the difficult method with a spot-on carrier frequency and with the upper sideband also audible. In the end, we also filter out the unwanted upper sideband.

Update 09/2017: I've later released a simple descrambler tool called deinvert. You should probably try that one instead; these old scripts will be preserved here though.

A determined 'hacker' decrypts RDS-TMC

As told in a previous post, I like to watch the RDS-TMC traffic messages every now and then, just for fun. Even though I've never had a car. Actually I haven't done it for years now, but thought I'd share with you the joy of solving the enigma.[disclaimer 1]

RDS-TMC is used in car navigators to inform the driver about traffic jams, roadworks and urgent stuff like that. It's being broadcast on a subcarrier of a public radio FM transmission. It's encrypted in many countries, including mine, so that it could be monetized by selling the encryption keys.

A draft of the encryption standard, namely ISO/DIS 14819-6, is freely available online. Here's an excerpt[disclaimer 2] that reads blatantly like a challenge:

"After calling for candidate proposals [for a method of encryption], the submission from Deutsche Telekom was judged by an expert panel to have best met the pre-determined criteria the task force had established. The method encrypts the sixteen bits that form the Location element in each RDS-TMC message to render the message virtually useless without decryption. The encryption is only 'light' but was adjudged to be adequate to deter other than the most determined 'hacker'. More secure systems were rejected because of the RDS capacity overhead that was required."

TMC messages consist mostly of numeric references to a static database of preset sentences and locations; no actual text is being transmitted. The database is not a secret and is freely available. The location information is encrypted with a key that changes daily. Every night, a random key is picked from 31 pregenerated alternatives. The key is never transferred over the air, only its numeric ID (1–31). The keys are preprogrammed into all licensed TMC receivers, and they can decrypt the locations knowing the key ID.

The size of the key space is 2¹⁶ and the encryption algorithm consists of three permutation operations:

The algorithm is simple enough to be run using pen-and-paper hardware, and that's just what I did while creating the above crypto diagram:

The tricky part is that I don't know the keys. But there's a catch. To save bandwidth, only regional messages are transmitted. This limits the space of possible locations, giving us a lot of information about the encrypted data. Assuming all messages are from this limited region, we can limit the number of keys to a very small number, in the dozens.

The next day, we have an all new encryption key again. But there's another catch. Many messages persist over several days, if not weeks. These would be messages about long-lasting roadworks and such. We just need to wait for messages that we heard yesterday that only have their location code changed, and we can continue limiting the keyspace by collecting more data.

Once we've limited the keyspace to a single key, we can decrypt all of today's messages. When the key changes again, it is trivial to find today's key by knowing yesterday's key and comparing the locations of persistent messages; this is known as a known-plaintext attack or KPA.

Here's some encrypted data straight from the radio.

$ ./redsea.pl | grep TMC
══╡ TMC msg 00 1828 4400
══╡ TMC sysmsg 6040
══╡ TMC msg 00 1828 4400
══╡ TMC msg 07 8264 0294
══╡ TMC msg 07 8264 0294
══╡ TMC msg 07 8264 0294
══╡ TMC sysmsg 0021
══╡ TMC msg 07 5964 72ca
█

A little Perl script then decodes everything and even plots the affected segment on a little map. The screenshot is from a few years back.

Now I just need a car. Well, actually I prefer motorcycles. But I guess it would work, too.

Tools used: Ordinary FM radio, sound card, computer. All data is from public sources. RDS was decoded from intermodulation distortion in the radio's Line Out audio caused by the stereo demuxer circuitry.

Update 2014-07-27: Some news seem to highlight that I was the first one to break this joke of a cipher. This could be true; I don't really care. In any case, the often-referred-to 2007 work by Barisani and Bianco (PDF 13MB) was done on unencrypted RDS-TMC and no cryptanalysis was involved; "encryption is supported for commercial services but irrelevant to our goals". I encourage you to read it, it addressed some of the real-world security implications of injecting crafted TMC messages into cars.

---

Disclaimer 1: I will take this post down on the first appearance of any complaint from any party, of course. My intent is not malicious and I'm not even publishing any keys or code.

Disclaimer 2: This use of the above excerpt of the ISO standard is not an infringement of copyright as it is being used here under the doctrine of "Fair Use" of the United States Copyright Law (17 U.S.C. § 107), seeing as this blog is hosted on US soil.

Rendering PCM with simulated phosphor persistence

When PCM waveforms and similar oscillograms are displayed on screen, computational speed is often preferred over beauty and information content. For example, Audacity only draws the local maximum envelope amplitude and (what appears to be) RMS power when zoomed out, and when zoomed in, displays a very straightforward linear interpolation between samples.

Here's the startup beep of my Kenwood TK-2302, rendered by Audacity:

Analogue oscilloscopes, on the other hand, do things differently. An electron beam scans a phosphor screen at a constant X velocity, lighting a dot everywhere it hits. The dot brightness is proportional to the time the electron beam was directed at it. Because the X speed of the beam is constant and the Y position is modulated by the waveform, brightness gives information about the local derivative of the function.

Of course, PCM is all about "dots" as well, so we could possibly mimic this behavior digitally. I'm going to simulate an electron beam by first oversampling the above waveform by an insane amount – at 1 megahertz, that is. Lowpass filtering follows, with a cutoff frequency at the Nyquist frequency of the original PCM. Now, a program reads in the processed PCM and for each sample will make the corresponding dot on the XY plane a little brighter. (Actually each sample will affect 4 image pixels because of bilinear interpolation.) This method gives us a much more interesting rendering:

Now how cool is that? It looks like an X-ray of the signal. We can see right away that the beep is roughly a square wave, because there's light on top and bottom of the oscillation envelope but mostly darkness in between. Minute changes in the harmonic content are also visible as interesting banding and ribbons.

At very high zoom, Audacity doesn't even bother reconstructing the actual waveform but just thinks of it as a "connect the dots" puzzle. This is computationally feasible, of course. Oversampling at 3,000,017 Hz and downpass filtering at the original Nyquist frequency, on the other hand, results in an apparent reconstruction of the analogue wave:

Finally, the soprano section of the Finnish Radio Chamber Choir singing a D note in a piece by Einojuhani Rautavaara:

Relevant code for scientific interest in this Gist.

Character recognition, the simple way

Recently I solved a small problem and found it funny enough to write a post.

I had a PDF document with numbers in it (ones and zeros). I needed the numbers for a program, but they were embedded as a scanned picture instead of text. Copying them by hand would be boring and error-prone. I wouldn't want any typos, seeing as the numbers themselves were supposed to be part of an error-correcting code.

Then I thought: perhaps Perl could do this for me! I came up with this:

#!/usr/bin/perl
use feature "switch";
 
open(S,"convert bitit.png gray:-|");
for $y (0..434) {
  for $x (0..699) {
    read(S,$a,1);
    $b[int($x / 27)][int($y / 27)] ++ if (ord($a) < 127);
  }
}
close(S);
 
for $y (0..15) {
  $byte = 0;
  for $x (0..25) {
    $byte <<= 1;
    given ($b[$x][$y] // 0) {
      when ($_ < 10) { print "  "; }
      when ($_ < 90) { print "1 "; $byte++; }
      default        { print "0 "; }
    }
  }
  printf (" 0x%07x\n",$byte);
}

Running the script produces:

$ perl bitit.pl 
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 1 1  0x2000077
0 1                           0 1 0 1 1 1 0 0 1 1 1  0x10002e7
0   1                         0 1 1 1 0 1 0 1 1 1 1  0x08003af
0     1                       0 1 1 0 0 0 0 1 0 1 1  0x040030b
0       1                     0 1 1 0 1 0 1 1 0 0 1  0x0200359
0         1                   0 1 1 0 1 1 1 0 0 0 0  0x0100370
0           1                 0 0 1 1 0 1 1 1 0 0 0  0x00801b8
0             1               0 0 0 1 1 0 1 1 1 0 0  0x00400dc
0               1             0 0 0 0 1 1 0 1 1 1 0  0x002006e
0                 1           0 0 0 0 0 1 1 0 1 1 1  0x0010037
0                   1         0 1 0 1 1 0 0 0 1 1 1  0x00082c7
0                     1       0 1 1 1 0 1 1 1 1 1 1  0x00043bf
0                       1     0 1 1 0 0 0 0 0 0 1 1  0x0002303
0                         1   0 1 1 0 1 0 1 1 1 0 1  0x000135d
0                           1 0 1 1 0 1 1 1 0 0 1 0  0x0000b72
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 1 1 1 0 0 1  0x00005b9
$ █

How does it do that? The script divides the image — read pixel-by-pixel via ImageMagick — into squares and counts the black pixels in every square. The character "0" has obviously more black than "1"; the threshold was found by experimenting. An empty square has nearly no black pixels at all, and depicts a zero in this example. Calculating a hex value for every row is simple.

I ended up having to write only slightly more characters than the image contained! :)