Bit scrambling FSK

[K5OKC]

As an exercise, now that I have my 4FSK test program working, I added a K9NG/G3RUH style bit-scrambler.

The object being to randomize any long runs of 0's or 1's in the codec output. Obviously I'm not going to get white-noise output on SSB, but I wondered what effect it would have on the tone amplitudes.

It does have an effect, but the changes in dB are not great. Maybe 1 dB. But you can see one tone that is high and one tone that is low, change to about equal amplitudes.

Another effect is it seems to remove the big signal at the center of the spectrum (1400 Hz).

73/Steve

[Steve]

Going for broke, I changed the tone oscillators to use Newman phases. The waveform is interesting, but the demodulator didn't like its oscillators set up like that, and was about 10 dB SNR worse, with poor audio quality. Even though it stayed in Sync.

[Matthew Cook]

Bit stuffing (https://en.wikipedia.org/wiki/Bit_stuffing) was popular in the day for preventing DC bias causing your data slicer on receive to shift unnecessarily, I'm not sure it would have much effect on TX.  

I've often wondered if DSP modems suffered the same way from DC as did the analog designs of the day.  It has evoked some quite interesting discussions here.  I lost weeks of my life doing bit stuffing on 8-bit micros for 1200, 9600 & 19200 bit/s packet modulators and relying on the Z85C30's SCC's to do the demodulation for me.

SDLC/HDLC bit stuffing by itself still has a small DC offset and also had the side effect of producing a bit stream of various lengths (dependant upon 1/0 combination).  There are other techniques like 8/10 encoding used on ethernet (to keep transformers from saturating due to DC) that might also yield an interesting result.   At the end of the day it's all about the Eb/n0 as David keeps telling me (*grin*).

I'm sure the mathematicians among us would be able to prove one way or the other the effectiveness of introducing DC balance into our bit streams.  Unfortunately this imagineer is too many years out of school to do the maths any longer.

73

Matthew

VK5ZM

--
You received this message because you are subscribed to the Google Groups "digitalvoice" group.
To unsubscribe from this group and stop receiving emails from it, send an email to digitalvoice+unsubscribe@googlegroups.com.
To post to this group, send email to digita...@googlegroups.com.
Visit this group at https://groups.google.com/group/digitalvoice.
For more options, visit https://groups.google.com/d/optout.

[Steve]

Another problem, is the scrambler is 17-bits long, so it needs time to fill before actual pseudo-random bits emerge. Thus the first 17-bits are not scrambled at all.

I was thinking, you could add 20 cycles (Fs / Rs) as a header when the transmitter first starts up. Some throwaway bits.

Anyway, it is pretty consistent at losing Sync the first two Frames. Heck, that's 128 bits lost, or 4 codec frames. :-)

As a comparison, the non-scrambled waveform only loses one frame at the beginning (64 bits).

So maybe the extra 20 cycles on startup might help it too.

73/Steve

[Stuart Longland]

On 26/05/17 15:01, Matthew Cook wrote:
>
> I've often wondered if DSP modems suffered the same way from DC as did
> the analog designs of the day. It has evoked some quite interesting
> discussions here. I lost weeks of my life doing bit stuffing on 8-bit
> micros for 1200, 9600 & 19200 bit/s packet modulators and relying on the
> Z85C30's SCC's to do the demodulation for me.

The other way of tackling this is symbols stuffing. The problematic
symbols are all zeros and all ones… replace those, and you can ensure
there's always a change in the bit pattern every N bits for you to keep
sync on.

One way I've seen it handled is to replace problematic byte sequences.
e.g. EDMI command-line protocol used by their energy meters, use 0x02
(STX) to represent the start of a frame and 0x03 (ETX) to represent the end.

Thus, if 0x02 or 0x03 appears anywhere in the middle, it causes
confusion. So to counteract this, they replace 0x02 with 0x10 0x42 (DLE
'B') and 0x03 with 0x10 0x43 (DLE 'C'). 0x10 itself is replaced with
0x10 0x50 (DLE 'P').

At the far end, they substitute the other way: 0x10 0x42 → 0x02, 0x10
0x03 → 0x03, 0x10 0x50 → 0x10.

You might choose to stuff a symbol rather than a whole byte, but the
concept is the same. You might decide that the symbol sequences
(represented here in base-4 number system to fit with 4-FSK) 00₃, 33₃
and 21₃ are sacred, so you substitute:

00₃ → 21₃ 20₃
33₃ → 21₃ 23₃
21₃ → 21₃ 21₃

If the receiver sees the symbol sequence 21₃, it then knows the next
symbol will be a 2₃ which is then followed by either 0₃, 1₃ or 3₃, a 2₃
is invalid.

That trade-off of using an entire symbol may make life a little easier.
--
Stuart Longland (aka Redhatter, VK4MSL)

I haven't lost my mind...
...it's backed up on a tape somewhere.

[Steve]

I just had a thought as to why the Newman phases (basically starting phases that are different for each tone, rather than just set to 1 + 0i) didn't work very well. It dawns on me that the FSK tones are one per symbol. I think Newman phases only works on multi-tone signals FDM.

Anyway, that makes sense to me, and thus was kind of silly to do it with single tones. Even if they are different tones each symbol.

73

[cardre]

Just some random thoughts...

I'm not sure if it applies in the circumstances you're trying, but data whitening is the term I've seen as well as maths and algorithms that are used to eliminate runs of 0s or 1s. 

It may even potentially be used as another form of error correction? If each known packet length should have a certain whitened value, bit flipping variations of received data after de-whitening may be used to try to find out original packet?

[Matthew Cook]

Don't forget many of these old analog systems relied on training sequences or preamble to aid in initial clock recovery, once you had acquired the bit stream you then waited for a frame sync or start symbol (usually 0xFE) which could never occur with 5-bit one & zero stuffing.  This meant that the scrambler was generally pre-loaded with  "1010 1010 1010 1010 1111 1110" which meant you had a better than average chance of getting useful output from the get go.  It was always a trade off on how long the preamble was to the data being sent.  This training overhead was a problem on short frames, but never a problem on streams.

73

Matthew

VK5ZM

[Stuart Longland]

Would a stream cipher with a fixed key be a way of achieving this?

Using something like RC4 with a hard-coded key (prominent in the
sources/specifications) to "scramble" the data for "data whitening"
purposes?

As a bonus, if you use something a little stronger than RC4, in
situations where you *do* need the privacy (e.g. commercial band, or in
a true emergency), you just need to negotiate a key which can be done
off-air if needed.

[Steve]

I used a modified RC4 in an experiment. It added a Counter Mode.

RC4 Counter Mode

This was basically a 24-bit counter that increments every frame. So that if a frame is corrupted, then you get a new stream on the next counter.

I got this idea from a Patent application from the 90's (about the time that WEP was found to be toast).

The nice thing about the 17-bits is it rolls-over very quickly, such that any data glitches don't blow the whole transmission.

The problem with a stream cipher, you have to relay the counter value to the other side. But since all the bandwidth is used by the vocoder, it would have to be via a side channel. Not very practical. Just sending the same RC4 bits over and over isn't random enough.

Another method, is to create a voice activity detector (VAT), and now you have data bandwidth available to send counters and text over, when the vocoder is emitting silence. Using a Unique Word that declares the frame data and not phone.

Anyway, that's the problem with stream ciphers as I see it. I'm not very learned in such matters though.

[Jeff Francis™]

  If you're serious about your bonus case (commercial encryption), don't use RC4. It's got multiple known vulnerabilities, and has been deprecated for TLS/SSL use because of that. For the primary (ham) case as a repeatable source of pseudorandom data, it should work great. As a bonus, it's trivial (and fast) to implement.

Jeff N0GQ

--
You received this message because you are subscribed to the Google Groups "digitalvoice" group.
To unsubscribe from this group and stop receiving emails from it, send an email to digitalvoice+unsubscribe@googlegroups.com.
To post to this group, send email to digita...@googlegroups.com.
Visit this group at https://groups.google.com/group/digitalvoice.
For more options, visit https://groups.google.com/d/optout.

--

-=jeff=-

[Stuart Longland]

On 03/06/17 00:24, Jeff Francis™ wrote:
> If you're serious about your bonus case (commercial encryption), don't
> use RC4. It's got multiple known vulnerabilities, and has been
> deprecated for TLS/SSL use because of that.

Agreed… This is why I suggested using something stronger than RC4 if
it's for any purpose other than scrambling to ensure randomness of the
modulated signal.

If encryption mattered, there's a list as long as my arm of potential
suspects: ACHTERBAHN-128, Grain 128a, HC-256, Phelix, Py, the Salsa20
family, SNOW 2/3G, SOBER-128, Scream, Turing, MUGI, Panama, ISAAC and Pike.

Yes, I've looked into this already¹.

All of those are open and not patent encumbered to the best of my
knowledge, and are reasonably strong. Some have commercial backing from
big players (e.g. Google threw its support behind ChaCha20 which is one
of the Salsa20 family of ciphers).

> For the primary (ham) case
> as a repeatable source of pseudorandom data, it should work great. As a
> bonus, it's trivial (and fast) to implement.

This was my thinking. If the key is specified in public documentation,
then use of it over the air is no different to people using AMBE/IMBE
on-air. In fact, AMBE/IMBE is worse as the only legal implementation is
a pre-programmed chip from DVSI.

Nobody cares how you choose to implement a stream cipher like RC4. :-)

1.
https://stuartl.longlandclan.id.au/blog/2017/03/26/digital-emergency-comms-ideas/

[Steve]

The problem with a noisy channel, is that data loss can occur. Mostly in short bursts, but often in deep fades. Thus, any cipher system needs to operate in this environment.

In packet radio, we normally sent 64 octet packets over HF. If this packet didn't pass the checksum at the other end, then it was tossed in the bit-bucket. You sent a negative to the sender (NAK) and the sender sent that packet again. The sender might try a few times, and if no success, it would close down and try again later.

The rule in cipher security is to not encrypt header information. There's a few reasons for this, but the main being that the header is repeated, so after a short time, you can figure out the key.

In ax25 packet, the header may be up to 70 bytes long, given a list of repeaters. Of course on HF you didn't use the digipeater function, as it lengthened the packet. Thus, 14 bytes (a source and destination callsign) was used. Added to that was two bytes of checksum. Leaving us with (64 - 14 - 2) 48 octets of information that could be sent per packet (25% overhead).

It is this (and only this) 48 octets that is encrypted.

Now the problem is, what kind of encryption? There are two choices: 1) stream, 2) block. Now obviously a stream cipher is not going to be a secure choice. Even if you used RC4 with a 256 octet key, it is going to output the same bits every time it starts. For example if the cipher has a key 0x01 then the stream might be:

6d 1c 28 8c 03 ff a0 33 

If the key is 0x02 then the stream might be:

8f 33 53 bd fb 90 eb 83

These octets are exclusive-or (XOR) with the plain-text data producing cipher-text data. The next eight octets will be something else, and the next eight, something else again. But! If you drop your Push-to-Talk, and then Push-to-Talk for the next transmission, the XOR stream is identical. So, continuing with the example above, your stream repeats itself every 48 octets. This is not secure. It's like pseudo-random numbers with the same seed. You get the same numbers every time you start the generator.

So, in radio systems, a block cipher with a counter mode (CTR) is used. Now you can make a block cipher into a stream cipher without modifying the internals. But you have to modify the engine if you want blocks out of a stream cipher.

So, we key the microphone. We want a different starting point every time. To do this, a counter is used. For example, take a 24 bit counter and randomly set a value. Now every 10 voice frames, you increment the counter and get a different XOR sequence. So this counter affects the key. Of course if the counter is always the same number, then you'll always get the same XOR sequence. The counter has to increment.

The neat thing about this counter, is that it doesn't have to be secret. The key is secret, the counter only stirs the pot.

So in radio, what we have to do is send this counter to the receiver. If this counter is incremented every 10 voice frames then you have to send the receiver the counter every 10 voice frames! Then before the next PTT, you set in a new random value to the counter.

Yes, this takes bandwidth. If you add the counter bits with the voice bits, then that is your data rate necessary. If you are already consuming 100% of your data rate, then there is no room for sending the counter. Obviously you need to create space.

One way of creating space in voice encryption (and not increasing the bit-rate), is to create a function called Voice Activity Detector (VAD). This algorithm examines the vocoder output and determines when silence is detected. If the silence is longer than the number of bits required for the counter, then presto, we set the VAD bit and send the counter. Then the receiver has to maintain sync until it receives the next counter. If a noise burst destroys the data, the data is garbage until the next counter is received. If it is five second later, then the receiver gets five seconds of comfort noise.

If someone made a VAD system for codec2, it would be a great boon to encryption over low bit-rate channels. For example, MELPE has a VAD that is used by PairPhone over a 1200 bit/s channel. Of course we don't want to use MELPE.

That's all I wanted to convey here. That a secure voice system uses a block cipher with a counter mode. You can't use a stream cipher, unless you modify the internals. Something I did with RC4. I created a counter mode out of a stream cipher, but it wasn't an add-on, it was a new engine (using the same S-box design).

Now, on the subject of bit-scrambling, then yes - a stream cipher is adequate. We actually want it to duplicate the stream. We even want it to duplicate the stream fast. For example the normal way is to use a Linear Feedback Shift Register (LFSR). Even with a small number of bits, say 13 bits. If the data is corrupted by the ether, then when the stream starts over, you again fall in sync. These are called Self-synchronizing stream ciphers. They are XOR just like cryptographically-secure stream ciphers, but are of course not secure.

Since the first 13 bits output from the LFSR are just the LFSR starting value, then the first 13-bits output are unscrambled. Thus, a system using an LFSR needs to have a header that gives time for the LFSR to increment. Generally, a 16 bit header is sufficient.

Is this too long? Suis-je un intello ?

Happy Saturday! Time to go mow the lawn (weeds)...