chirp.io is a site/app for sharing e.g a photo identified by a short FSK audio chirp. The chirp is 10 symbols of data, then 8 symbols of error correction. These symbols are 32-valued (5 bits/symbol) and the error correcting code is a Reed-Solomon code. Thus, a chirp is the output of an $ RS[n,k,t]$ $= RS[18, 10, 4]$ encoder over the field $GF(32)$ or $\mathbb F_{2^5}$. These details are from a partial description of the chirp.io protocol

An example chirp is gfhd9532dm (base 32) for which the error parity symbols are 4fbeu0mo. Given this information is it possible to determine the other parameters (e.g. the generator polynomial of the Galois/finite field) of the coder, in order to check/correct a received chirp?

So far I've systematically tried candidate parameters (i.e brute force search) with trials.py but without success.

ETA: api.chirp.io returns a chirp (and parity symbols) in response to a JSON POST. e.g.

$ curl -X 'POST' -H 'Content-Type: application/json' \
       -d '{"body":"abc","mimetype":"text/plain","title":"abc"}' \
{"longcode": "ovkp99793iao89q5ku", "shortcode": "ovkp99793i", "is_new": 1}

I'm guessing that making more than a few such requests would trigger blocking or rate limiting, and doing so without express permission isn't something I'm willing to do.

ETA 2017-02-05: The original Chirp app has been discontinued, the above request now returns HTTP 404.

  • $\begingroup$ I see in trials.py that you have two other example chirps, srg00lgbif 4c6u07sq and 0b07407074 9lir5uo0. Do you have a means of generating those? I didn't see any examples in the documentation. $\endgroup$
    – Snowball
    Feb 7, 2014 at 23:20
  • $\begingroup$ These two obtained by recording a chirp wave form, and eye-balling a spectrogram to match frequencies. The first is from ricardo.cc/2012/12/30/…, the second is one I did. $\endgroup$ Feb 8, 2014 at 16:14
  • $\begingroup$ That ain't a technical spec :-/ Too many guesses needed: are they using a normal basis or a monomial basis for representing a field element? If the latter (my first guess), are they using a big-endian or the opposite? Which primitive polynomial (will affect on the natural choices of consecutive powers)? If I had a ready-made piece of code interpreting those base-32 symbols as bit sequences, I might give it a try. But ... your first attempts probably would be same as mine: little-endian, primitive polynomial $x^5+x^2+1$, generator polynomial $\prod_{i=0}^6(x-\alpha^i)$. $\endgroup$ Feb 15, 2014 at 7:29
  • $\begingroup$ If that didn't work I would lose heart very quickly, and give up. Mind you, RS-codes are maximum distance separable, so its parameters should be $(18,10,9)$, i.e. capable of correcting four errors. Sorry to sound so negative, but really you should be able to find this piece of information from a technical spec. That's exactly why engineers write those specs! $\endgroup$ Feb 15, 2014 at 7:29
  • $\begingroup$ @moreati: Perhaps this is against the spirit of the question, but have you considered asking the chirp.io folks what parameters they're using? I'm sure they'd like to see their protocol succeed, and it's more likely to succeed if there are multiple implementations. $\endgroup$
    – Snowball
    Feb 17, 2014 at 20:24

2 Answers 2


From just the information given (that one codeword of a systematic $RS[18,10,4]$ code is gfhd9532dm4fbeu0mo), it is not possible to identify what the code is or how the finite field was set up as binary $5$-tuples etc. The problem is better viewed as attempting to determine a hashing function that maps gfhd9532dm onto 4fbeu0mo from just the results of this single hash. Many hashing functions will give this result, and even if one is found (and even if it seems to fit what a Reed-Solomon encoder would be expected to do), there is no reason to believe that the function is the correct one and will work on the next 10 data symbols too. From a cryptographic perspective, you have a known plaintext attack with a single plaintext available. Multiple known plaintexts would be better, and a chosen plaintext attack where you are allowed to specify the data symbols (especially with multiple chosen plaintexts) would be even better.


Actually, there is one paper that's exactly looking into this issue:

Zahedi, A., & Mohammad-Khani, G. R. (2012). "Reconstruction of a non-binary block code from an intercepted sequence with application to reed-solomon codes". IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences, 95(11), 1873-1880.

Abstract: In this paper, a method is proposed for reconstruction of the parameters of a non-binary block encoder using an intercepted sequence of noisy coded data. The proposed method is a generalization of the Barbier's method for the reconstruction of binary block codes to the more problematic case of non-binary codes. It has been shown mathematically that considering some revisions in definitions, such a generalization is possible. The proposed method is able to estimate the code parameters such as the code length, the code dimension, number of bits per symbol, and the dual-code subspace, and also to synchronize the sequence. Since the Reed-Solomon code is the most important type of non-binary block codes, an additional method is proposed to reconstruct the generator polynomial in the case of Reed-Solomon codes. The proposed method is evaluated via computer simulations which verify its strength and effectiveness.

However, I don't know how their algorithms work since I could not get an access to the paper, but you can buy it online if you really need it.

  • 1
    $\begingroup$ Thank you, I'll look into that. I tried to use Automatic Recognition and Classification of Forward Error Correcting Codes by J. F. Ziegler (2000). Unfortunately I have neither Matlab, nor sufficient mathematical knowledge to adapt it to Octave. My WIP is at github.com/moreati/ziegler2000 $\endgroup$ May 20, 2015 at 13:08
  • $\begingroup$ Thank you for the pointer, I'll look into that too! Good luck in your endeavour, I will probably try to implement something like that too in the future, but right now I'm more focused on list decoding to go beyond the singleton bound :) However you should be able to adapt a Matlab code to Octave quite easily if you have enough time to debug it from my experience, but if it's possible, I advise you to borrow a Matlab copy from someone and try to run the code first, so that you know the normal output (so that you can compare to your Octave conversion). Just follow the Octave warnings. $\endgroup$
    – gaborous
    May 20, 2015 at 21:57
  • $\begingroup$ I've found another paper that may offer a suitable algorithm: Lu Ouxin, Gan Lu and Liao Hongshu, 2015. Blind Reconstruction of RS Code. Asian Journal of Applied Sciences, 8: 37-45. This one is free to download. $\endgroup$ Jun 11, 2015 at 20:20
  • $\begingroup$ Nice finding, thank's for reporting it! The algorithm seems quite simple, there are only 3 steps and they all use non-novel algorithms/data structures, so yes it should be implementable. However I think the details are scarce, I hope they didn't miss out some necessary tricks that may make this harder to implement... (why so many CS papers aren't including pseudo-codes to describe algorithms is beyond me). $\endgroup$
    – gaborous
    Jun 11, 2015 at 20:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .