Thursday, January 12, 2017

Fast forwarding the std::next_permutation algorithm

I started my computer with a project that looks more and more like Sisyfos work.

It is trying to solve a puzzle by running through a set of permutations, and it is using std::next_permutation.

However, a day into the computation I realized that the algorithm could be further improved. Should I stop the calculation and restart it? Or let it continue, with the ineffective algorithm?

Looking at the internet I found an in depth explanation of std::next_permutation Implementation Explanation. std::next_permutation will from a starting point increase the permutation in an lexical fashion until it rolls over and returns false:

std::vector<int> skip_next_list = { 1,2,3,4, 5, 6, 7, 8, 9, 10, 11};
do {
//some work here
} while (std::next_permutation(skip_next_list.begin(), skip_next_list.end()));


My search had reached 309000000 when I aborted the job, so I needed to fast forward to that point. I realized that for 6 iterations (3!) it would update the last three entries of skip_next_list, for 24 (4!) the last four and so on.

So this is the skip_next_permutation function, fast forwarding to a number far into the sequence of std::next_permutation.

template<typename It> void skip_next_permutation(uint64_t skip_num, It begin, It end)
{
 if (skip_num <= 0) return; // does not have to be an error

 //build a lut of factorials, this could be a static
 std::vector<uint64_t> factorials;
 factorials.push_back(1); ///  0! == 1
 long idx = 1;
 long input_length = end - begin;
 do {
  factorials.push_back(factorials[idx-1] * idx);
 } while (factorials[++idx - 1] <= skip_num); //

 // now start to loop, find the factorial that is one smaller than the number we want to skip forward
 long my_inc = factorials.size() - 2; // always 2 lower than factorials.size()

 do
 {
  int quotient = skip_num / factorials[my_inc];
  skip_num = skip_num%factorials[my_inc]; //the remaider are the remaining skip_num

  if (skip_num == 0 && quotient == 0) goto end_loop;
  std::swap(begin[input_length - my_inc - 1], begin[input_length - my_inc + quotient - 1]);
  std::sort(begin + input_length - my_inc, end); //avoid with clever management?
  my_inc--;
 } while (my_inc >= 1);
end_loop:
 return;
}
The following table shows the factorials std::next_permutation algorithm exhausted, the number used for skip_next_permutation and the time std::next_permutation used.


Factorial
Number
Time / ms
9!
362 879
0.9
12!
39 916 799
94.1
13!
6 227 020 799
14 436.6


The fast forward function skip_next_permutation uses approximately 0.009 ms for all the values.

Monday, November 28, 2016

More sensors for Tellstick local access

After obtaining local network access to the Tellstick net I also have a wind sensor and a rain sensor close to my Tellstick net. Again, translating the Telldus .cpp code to python, the following python code gives the same results as the Telldus Live page. The code for the 1984/1994 sensors are identical except for the:
checksum = checksum + 0x1 + 0x9 + 0x8 + 0x4
vs
checksum = checksum + 0x1 + 0x9 + 0x9 + 0x4
checksum calculation. Here are the python code.
def decode2914(inp):
#source:telldus-core/service/ProtocolOregon.cpp@c9567f
#// rain
value = int(inp, 16)
messageChecksum1 = value & 0xF
value  = value >> 4
messageChecksum2 = value & 0xF
value  = value >> 4
totRain1 = value & 0xF
value  = value >> 4
totRain2 = value & 0xF
value  = value >> 4
totRain3 = value & 0xF
value  = value >> 4
totRain4 = value & 0xF
value  = value >> 4
totRain5 = value & 0xF
value  = value >> 4
totRain6 = value & 0xF
value  = value >> 4
rainRate1 = value & 0xF
value  = value >> 4
rainRate2 = value & 0xF
value  = value >> 4
rainRate3 = value & 0xF
value  = value >> 4
rainRate4 = value & 0xF
value  = value >> 4
battery = value & 0xF #// PROBABLY battery
value  = value >> 4
rollingcode = ((value >> 4) & 0xF) + (value & 0xF)
checksum =    ((value >> 4) & 0xF) + (value & 0xF)
value  = value >> 8
channel = value & 0xF
checksum = checksum + totRain1 + totRain2 + totRain3 + totRain4 + totRain5 + totRain6 +\
rainRate1 + rainRate2 + rainRate3 + rainRate4 +\
battery + channel + 0x2 + 0x9 + 0x1 + 0x4
if (((checksum >> 4) & 0xF) != messageChecksum1 or (checksum & 0xF) != messageChecksum2):
#// checksum error
return ""
totRain = ((totRain1 * 100000) + (totRain2 * 10000) + (totRain3 * 1000) +\
(totRain4 * 100) + (totRain5 * 10) + totRain6)/1000.0*25.4
rainRate = ((rainRate1 * 1000) + (rainRate2 * 100) + (rainRate3 * 10) + rainRate4)/100.0*25.4

return "%f\t%f"%(totRain, rainRate)



def decode1994(inp):
#source:telldus-core/service/ProtocolOregon.cpp@c9567f
#wind
value = int(inp, 16)
crcCheck = value & 0xF
value  = value >> 4
messageChecksum1 = value & 0xF
value  = value >> 4
messageChecksum2 = value & 0xF
value  = value >> 4
avg1 = value & 0xF
value  = value >> 4
avg2 = value & 0xF
value  = value >> 4
avg3 = value & 0xF
value  = value >> 4
gust1 = value & 0xF
value  = value >> 4
gust2 = value & 0xF
value  = value >> 4
gust3 = value & 0xF
value  = value >> 4
unknown1 = value & 0xF
value  = value >> 4
unknown2 = value & 0xF
value  = value >> 4
direction = value & 0xF
value  = value >> 4
battery = value & 0xF  #// PROBABLY battery
value  = value >> 4
rollingcode = ((value >> 4) & 0xF) + (value & 0xF)
checksum =    ((value >> 4) & 0xF) + (value & 0xF)
value  = value >> 8
channel = value & 0xF
checksum = checksum + unknown1 + unknown2 + avg1 + avg2 + avg3 + gust1 + gust2 + gust3 + direction + battery + channel
checksum = checksum + 0x1 + 0x9 + 0x9 + 0x4
if (((checksum >> 4) & 0xF) != messageChecksum1 or (checksum & 0xF) != messageChecksum2):
#// checksum error
return ""
avg = ((avg1 * 100) + (avg2 * 10) + avg3)/10.0
gust = ((gust1 * 100) + (gust2 * 10) + gust3)/10.0
directiondegree = 22.5 * direction
return '%f\t%f\t%f'%(avg, gust, directiondegree)

def decode1984(inp):
#source:telldus-core/service/ProtocolOregon.cpp@c9567f
#// wind
value = int(inp, 16)
crcCheck = value & 0xF
value  = value >> 4
messageChecksum1 = value & 0xF
value  = value >> 4
messageChecksum2 = value & 0xF
value  = value >> 4
avg1 = value & 0xF
value  = value >> 4
avg2 = value & 0xF
value  = value >> 4
avg3 = value & 0xF
value  = value >> 4
gust1 = value & 0xF
value  = value >> 4
gust2 = value & 0xF
value  = value >> 4
gust3 = value & 0xF
value  = value >> 4
unknown1 = value & 0xF
value  = value >> 4
unknown2 = value & 0xF
value  = value >> 4
direction = value & 0xF
value  = value >> 4
battery = value & 0xF  #// PROBABLY battery
value  = value >> 4
rollingcode = ((value >> 4) & 0xF) + (value & 0xF)
checksum =    ((value >> 4) & 0xF) + (value & 0xF)
value  = value >> 8
channel = value & 0xF
checksum = checksum + unknown1 + unknown2 + avg1 + avg2 + avg3 + gust1 + gust2 + gust3 + direction + battery + channel
checksum = checksum + 0x1 + 0x9 + 0x8 + 0x4
if (((checksum >> 4) & 0xF) != messageChecksum1 or (checksum & 0xF) != messageChecksum2):
#// checksum error
return ""
avg = ((avg1 * 100) + (avg2 * 10) + avg3)/10.0
gust = ((gust1 * 100) + (gust2 * 10) + gust3)/10.0
directiondegree = 22.5 * direction

return '%f\t%f\t%f'%(avg, gust, directiondegree)
Just add some more checks in the while loop
while 1:
try:
data,(address, port) = sock.recvfrom(1040)
#print data
if (data.split(":")[6][6:10]=="F824"):
#print data.split(":")[7][5:5+14]
print decodeF824(data.split(":")[7][5:5+14])
elif (data.split(":")[6][6:10]=="1984"):
#print data.split(":")[7][5:5+16]
print decode1984(data.split(":")[7][5:5+16])
elif (data.split(":")[6][6:10]=="2914"):
#print data.split(":")[7][5:5+16]
print decode2914(data.split(":")[7][5:5+16])
else:
print data
#fp.write(data + '\n');
#fp.flush()
except KeyboardInterrupt:
print "done"
#fp.close()
break
except: # time out, try again
pass


Friday, November 25, 2016

Local access to Tellstick net via python

I installed a Tellstick net and were pretty baffled that there were no obvious way to access the thing locally. At least according to my internet search.

Telldus are providing source codes for free, the only problem seems to be how the information is arranged.

By piecing together information found various places I came up with the following:

Send an udp message on port 30303, all Tellstick net devices on the local network will respond to this with a string containing some unit specific information AND the IP address on the network.

sock.sendto(DISCOVERY_PAYLOAD, (DISCOVERY_ADDRESS, DISCOVERY_PORT))
data, (address, port) = sock.recvfrom(1024)

Then send a command that will make the Tellstick net echo the sensor information back via upd:

sock.sendto("11:reglistener", (address, 42314)) #I really love those port numbers

Read the upd port and filter for the sensors you want. This is how a Oregon model F824 output could look like:

7:RawDatah5:class6:sensor8:protocol6:oregon5:modeliF824s4:datai20E1730096074Ass

There are a lot regarding decoding Oregon data on the internet, I translated the telldus-core .cpp to python.

And it works, sometimes the output can be .1C or 1% humidity off compared to my Oregon display. The values match the values from Telldus Live though.

import socket
from datetime import timedelta
import time
def decodeF824(inp):
#source:telldus-core/service/ProtocolOregon.cpp@c9567f
value = int(inp, 16)
crcCheck = value & 0xF
value = value>>4
messageChecksum1 = value & 0xF
value = value >>4
messageChecksum2 = value & 0xF
value = value >> 4
unknown = value & 0xF
value = value >> 4
hum1 = value & 0xF
value = value >> 4
hum2 = value & 0xF
value = value >> 4
neg = value & 0xF
value = value >> 4
temp1 = value & 0xF
value = value >> 4
temp2 = value & 0xF
value = value >> 4
temp3 = value & 0xF
value = value >> 4
battery = value & 0xF
value = value >> 4
rollingcode = ((value >> 4) & 0xF) + (value & 0xF)
checksum = ((value >> 4) & 0xF) + (value & 0xF)
value = value >> 8
channel = value & 0xF
checksum += unknown + hum1 + hum2 + neg + temp1 + temp2 + temp3 + battery + channel + 0xF + 0x8 + 0x2 + 0x4
if ((((checksum >> 4) & 0xF) != messageChecksum1) or ((checksum & 0xF) != messageChecksum2)):
return ""
temperature = ((temp1 * 100) + (temp2 * 10) + temp3)/10.0
if (neg):
temperature = -temperature
humidity = (hum1 * 10.0) + hum2
retStr = "class:sensor;protocol:oregon;model:F824;id:"  #14;temp:0.0;humidity:46;
retStr = '%s%d;temp:%1.1f;humidity:%d;'%(retStr,rollingcode,temperature,humidity)
return retStr


DISCOVERY_PORT = 30303
DISCOVERY_ADDRESS = '<broadcast>'
DISCOVERY_PAYLOAD = b"D"
DISCOVERY_TIMEOUT = timedelta(seconds=5)
sock = socket.socket(socket.AF_INET, socket.SOCK_DGRAM)
sock.setsockopt(socket.SOL_SOCKET, socket.SO_BROADCAST, 1)
sock.setsockopt(socket.SOL_SOCKET, socket.SO_REUSEADDR, 1)
sock.settimeout(DISCOVERY_TIMEOUT.seconds)
sock.sendto(DISCOVERY_PAYLOAD, (DISCOVERY_ADDRESS, DISCOVERY_PORT))
data, (address, port) = sock.recvfrom(1024)
print data, address, port
time.sleep(1)
#fp = open("tellstick.data", "w")
print "listening..."
#UDPSock.sendto("A:disconnect", (address,42314)) #will reboot the Tellstick net
sock.sendto("11:reglistener", (address, 42314))
while 1:
try:
data,(address, port) = sock.recvfrom(10240)
print data
if (data.split(":")[6][6:10]=="F824"):
print decodeF824(data.split(":")[7][5:5+14])
#fp.write(data + '\n');
#fp.flush()
except KeyboardInterrupt:
print "done"
#fp.close()
break
except: # time out, try again
pass

Wednesday, October 12, 2016

A license system using Crypto++ with RSA keys

If someone really wants to hack your software they can. Sony tried to make copying impossible and ended up in court. My take is the same as when I lock my bike. It is not difficult to take the bike but you have to make a thief of yourself in order to do it.

Crypto++ is found here.

Step one in this process is to obtain some specifics regarding the hardware of the PC running your software. Serial numbers from hard drives, volume serial numbers, amount/speed of RAM. Anything can be used, note also the possible hassle your paying customers will suffer if they do anything to their PC at a later stage.

Hash this number, for Crypto++ this could be done something like this:

std::string SHA256HashString(std::string aString) {
 std::string digest;
 CryptoPP::SHA256 hash;

 CryptoPP::StringSource foo(aString, true,
  new CryptoPP::HashFilter(hash,
   new CryptoPP::HexEncoder(
    new CryptoPP::StringSink(digest))));

 return digest;
}
Make your customer send you this number. It is not feasible to recreate their hardware ID from this hash.


Step two is preparing your private and public keys.

 AutoSeededRandomPool rng;

 ...

 RSA::PrivateKey rsa_private;
 rsa_private.GenerateRandomWithKeySize(rng, 512); //select your keysize here
 bool isok = rsa_private.Validate(rng, 3);//Always check certificates your
       //program reads from external sources
 ByteQueue private_queue;
 rsa_private.Save(private_queue);

 FileSink private_file_sink("private.bin");
 private_queue.CopyTo(private_file_sink);
 private_file_sink.MessageEnd();

Just save the private key as a binary, nobody will look into this file, you could choose to do the same with the public key. I chose to hard code this file into my application, so I will save it as a base64 encoded string.

 RSA::PublicKey rsa_public(rsa_private);
 isok = rsa_public.Validate(rng, 3);
 ByteQueue public_queue;
 rsa_public.Save(public_queue);
 string ss_base64;
 Base64Encoder base64encoder_sink(new StringSink(ss_base64));
 public_queue.CopyTo(base64encoder_sink);
 base64encoder_sink.MessageEnd();
 cout << ss_base64 << endl;

 ofstream file_b64("public.b64");
 file_b64 << ss_base64;
 file_b64.close();

Step three is signing a file containing the information from step one. For me this a line containing the customers name and a line containing the hardware id hash.

 RSASSA_PKCS1v15_SHA_Signer signer(rsa_private);
// Create signature space
 size_t length = signer.MaxSignatureLength();
 SecByteBlock signature(length);

 // Sign message
 length = signer.SignMessage(rng, (const byte*)message.c_str(),
  message.length(), signature);

 // Resize now we know the true size of the signature
 signature.resize(length);

 string sig_string((char*)signature.data(), signature.size());
 Base64Encoder encoder;
 encoder.Put((byte*)sig_string.c_str(), sig_string.size());
 encoder.MessageEnd();
 word64 size = encoder.MaxRetrievable();
 string encoded;
 if (size)
 {
  encoded.resize(size);
  encoder.Get((byte*)encoded.data(), encoded.size());
 }
 cout << encoded << endl;
 ofstream file_b642("signature.b64");
 file_b642 << encoded;
 file_b642.close();

In order to keep everything in one file I now append the base 64 signature to the customer information.


 Customer name, place
 hardware id hash
 ----
 mflkdhjgs6fdli9456fjgdklSDGty5ftgd
 MDSWFrt+wegGgGmorebase64charshere


I will call this file "license.txt" and send it to the customer.

Step four. My application reads the hardware info, hashes it and compares it with the hash in the license.txt file. If it matches I will verify the hash with the signature. This way I know the hardware hash is not just copied.
A routine to decode base 64:

string b64_decoder(string b64_str)
{
 Base64Decoder b64_decoder;
 b64_decoder.Put((byte*)b64_str.data(), b64_str.size());
 b64_decoder.MessageEnd();
 string decoded_str;
 word64 size = b64_decoder.MaxRetrievable();
 if (size && size <= SIZE_MAX)
 {
  decoded_str.resize(size);
  b64_decoder.Get((byte*)decoded_str.data(), decoded_str.size());
 }
 else
 {
  decoded_str = "";
 }
 return decoded_str;
}
Step five recreates the public certificate, creates a verifier and checks the message vs the signature. Begin by debase64 both the public key and the signature:


 size_t pos = license_txt.find("----", 0); //Check your findings...
 string message_txt = trim(license_txt.substr(0, pos));
 string signature = b64_decoder(trim(license_txt.substr(pos + 4)));

 string public_b64 = "hm+560dXdR4dmorebase64charshere"

//rsa_public
 string rsa_public_str = b64_decoder(public_b64);
 RSA::PublicKey rsa_public;
 StringSource stringSource(rsa_public_str, true);
 rsa_public.BERDecode(stringSource);
 if (!rsa_public.Validate(rng, 3))
 {
  //if this is wrong someone has actually tampered with the code
 }
// Verifier object
 RSASSA_PKCS1v15_SHA_Verifier verifier(rsa_public);

 // Verify
 bool result = verifier.VerifyMessage((const byte*)message_txt.c_str(),
  message_txt.length(), (const byte*)signature.data(), signature.size());

 // Result
 if (true == result) {
  cout << "All OK" << endl;
 }
 else {
  cout << "bah bah baaaaa" << endl;
 }
Well, this is my implemetion at least.

Friday, January 22, 2016

Obtaining the external WAN IP address from a Netgear WNR2000v5

Earlier I used a DNS service in order to get the IP address of my internet connection. I used some free ones, and they worked very well. Until they didn't work.

Then I used an external server, like duckduckgo.com, utilizing the computer, with python, already running in my house. Something like:

adr = "https://duckduckgo.com/?q=what+is+my+ip&ia=answer"
req = urllib2.Request(adr)
res = urllib2.urlopen(req)
data = res.read()
res.close()
...
p = re.compile('\"Answer\":"Your IP address is (\d*).(\d*).(\d*).(\d*) in')
m = p.search(data)
...
current_ip = (m.groups()[0], m.groups()[1], m.groups()[2], m.groups()[3])
...

This data were then uploaded to a know web page if it were different from the previous address.

And that worked great, until I occasionally started to use a VPN service on the machine running the script. Then duckduckgo.com returned the IP address of my VPN, which would not forward my ssh logins to my home.


So I checked my router, Netgear WNR2000v5, and it returned the IP address as expected. But only from the page "RST_conn_status.htm". It would also return "Access denied" for the first login attempt if someone had logged in to the router for another machine. And it required a username/password.

The script then became:

username='admin'
password='password'
adr = 'http://10.0.0.1/RST_conn_status.htm'
try:  #if someone else logged in to the router we get access denied the first time
 req = urllib2.Request(adr)
 base64string = base64.encodestring('%s:%s'%(username, password)).replace('\n', '')
 req.add_header("Authorization", "Basic %s" % base64string)   
 res = urllib2.urlopen(req)
except:
 time.sleep(1)
req = urllib2.Request(adr)
base64string = base64.encodestring('%s:%s' % (username, password)).replace('\n', '')
req.add_header("Authorization", "Basic %s" % base64string)   
res = urllib2.urlopen(req)
time.sleep(1)
data = res.read()
res.close()
...
p = re.compile('var info_get_wanip=\"(\d*).(\d*).(\d*).(\d*)\";')
m = p.search(data)
...
current_ip = (m.groups()[0], m.groups()[1], m.groups()[2], m.groups()[3])
...


Saturday, October 4, 2014

Studying the TPMS signals from Subaru a.k.a. Schrader signals

1) Observing the car at standstill produced no signals. Even after driving.

Data collection: So far windows and HDSDR have been used. SDR# is not available to me, Neither a portable coputer with gnuradio. Recordings produced files that ended like this: 433789kHz_RF.wav Stereosignals in Audacity with something that looked like quadrature detection. Is this the I/Q?

2) While driving, an some signals were registered, approx one every 14 seconds.


The first part of the signal is constant, the second part varies.  48 bits. 8 first bits a short pulse. The second part is closer to the resonance frequency. Driving on, I never manage to observe this signal again. Maybe a local, exterior signal?


3) After some fiddeling with parameters, some other signal are observed.

I first processed these data with a low pass filter, then a normalization. Not wise, a repeating signal is also observed without the initial low pass filter:



Eight groups of packets, separated by 100 ms.



The packets are not yet analyzed, could this signal shape indicate FSK? Seems to be three different pulse lengths in the packet.  Like Jared Boon is taking about here.

Screendump from HDSDR:



Monday, September 29, 2014

Decoding Biltema Weatherstation 84086 / sensor 84056


This weather station is sold with one remote sensor and a base station capable of monitoring airpressure. It also have a radio controlled clock.

The remote sensor is capable of measuring temperature and pressure and broadcast this information on the 433 MHz band.

Using a 433 MHz receiver together with a logic analyzer several things could be learned:

The sensor transmit 20 bits of information starting with a 1.45 ms pulse followed by 1.50 ms silence. Pulses 2.16 ms long followed by 0.77 ms silence is '1', and 0.70 ms pulses followed by 2.23 ms silence is representing '0'.


Channel 2, -16.6C, 20% humidity

Several different measurements obtained with varying temperatures and constant humidity (36% (0b100100)) showed that the sensor transmitted the humidity in the seven last bits of the transmission.

The last seven bits is arranged in the following fashion: bit 1, 0 , 6, 5, 4, 3 and 2.

Yeah, and after some googling I found that the decoded signals were presented at telldus.com.

In the following table this decoding is used with the exception of me rotating the bitorder.