Arduino Forum

Using Arduino => Programming Questions => Topic started by: simsam on May 16, 2018, 02:29 pm

Title: Implementing Pairing Based Crypto on arduino uno
Post by: simsam on May 16, 2018, 02:29 pm
I have implemented Digital Signature using PBC   (https://crypto.stanford.edu/pbc/manual/ch01.html) and GMP libraries.( I have taken the code from the PBC library as liked above.)My code works correctly when i compile it on Visual Studios 2010.

Now i have to convert it and make it work on my arduino uno. For this i have used Visual Micro plugin. (i am able to run the arduino builtin examples from this) but the pbc code is causing alot of errors. The error log is attached below. I dont know what changes to make in the code to make it run in the arduino.

Code: [Select]
Error   1   10:23: fatal error: WinSDKVer.h: No such file or directory  C:\Users\name\Documents\Arduino\ArduinoClient\targetver.h   10 
3   IntelliSense: expected an identifier    c:\program files (x86)\microsoft sdks\windows\v7.0a\include\winuser.h   5341    3   
35  IntelliSense: identifier "EBADMSG" is undefined c:\program files (x86)\microsoft visual studio 10.0\vc\include\system_error 31  16 
42  IntelliSense: identifier "ECANCELED" is undefined   c:\program files (x86)\microsoft visual studio 10.0\vc\include\system_error 78  23 
36  IntelliSense: identifier "EIDRM" is undefined   c:\program files (x86)\microsoft visual studio 10.0\vc\include\system_error 47  23 
38  IntelliSense: identifier "ENODATA" is undefined c:\program files (x86)\microsoft visual studio 10.0\vc\include\system_error 63  25 
37  IntelliSense: identifier "ENOLINK" is undefined c:\program files (x86)\microsoft visual studio 10.0\vc\include\system_error 61  12 
39  IntelliSense: identifier "ENOSR" is undefined   c:\program files (x86)\microsoft visual studio 10.0\vc\include\system_error 67  24 
40  IntelliSense: identifier "ENOSTR" is undefined  c:\program files (x86)\microsoft visual studio 10.0\vc\include\system_error 74  17 
45  IntelliSense: identifier "ENOTRECOVERABLE" is undefined c:\program files (x86)\microsoft visual studio 10.0\vc\include\system_error 91  26 
41  IntelliSense: identifier "ENOTSUP" is undefined c:\program files (x86)\microsoft visual studio 10.0\vc\include\system_error 77  18 
48  IntelliSense: identifier "EOVERFLOW" is undefined   c:\program files (x86)\microsoft visual studio 10.0\vc\include\system_error 99  20 
43  IntelliSense: identifier "EOWNERDEAD" is undefined  c:\program files (x86)\microsoft visual studio 10.0\vc\include\system_error 83  15 
44  IntelliSense: identifier "EPROTO" is undefined  c:\program files (x86)\microsoft visual studio 10.0\vc\include\system_error 85  19 
46  IntelliSense: identifier "ETIME" is undefined   c:\program files (x86)\microsoft visual studio 10.0\vc\include\system_error 92  19 
47  IntelliSense: identifier "ETXTBSY" is undefined c:\program files (x86)\microsoft visual studio 10.0\vc\include\system_error 93  19 
49  IntelliSense: identifier "pairing_t" is undefined   c:\libs\pbc\include\pbc_test.h  10  42 
4   IntelliSense: invalid combination of type specifiers    c:\program files (x86)\microsoft visual studio 10.0\vc\include\yvals.h  536 14 
2   IntelliSense: invalid redeclaration of member function "HardwareSerial::write(uint8_t)" (declared at line 129)  c:\program files (x86)\arduino\hardware\arduino\avr\cores\arduino\hardwareserial.h  132 19  ArduinoClient
5   IntelliSense: the global scope has no "acosl"   c:\program files (x86)\microsoft visual studio 10.0\vc\include\cmath    28  13 
6   IntelliSense: the global scope has no "asinl"   c:\program files (x86)\microsoft visual studio 10.0\vc\include\cmath    28  32 
8   IntelliSense: the global scope has no "atan2l"  c:\program files (x86)\microsoft visual studio 10.0\vc\include\cmath    29  32 
7   IntelliSense: the global scope has no "atanl"   c:\program files (x86)\microsoft visual studio 10.0\vc\include\cmath    29  13 
9   IntelliSense: the global scope has no "ceill"   c:\program files (x86)\microsoft visual studio 10.0\vc\include\cmath    29  52 
11  IntelliSense: the global scope has no "coshl"   c:\program files (x86)\microsoft visual studio 10.0\vc\include\cmath    30  31 
10  IntelliSense: the global scope has no "cosl"    c:\program files (x86)\microsoft visual studio 10.0\vc\include\cmath    30  13 
12  IntelliSense: the global scope has no "expl"    c:\program files (x86)\microsoft visual studio 10.0\vc\include\cmath    30  50 
13  IntelliSense: the global scope has no "fabsl"   c:\program files (x86)\microsoft visual studio 10.0\vc\include\cmath    31  13 
14  IntelliSense: the global scope has no "floorl"  c:\program files (x86)\microsoft visual studio 10.0\vc\include\cmath    31  32 
15  IntelliSense: the global scope has no "fmodl"   c:\program files (x86)\microsoft visual studio 10.0\vc\include\cmath    31  52 
16  IntelliSense: the global scope has no "frexpl"  c:\program files (x86)\microsoft visual studio 10.0\vc\include\cmath    32  13 
17  IntelliSense: the global scope has no "ldexpl"  c:\program files (x86)\microsoft visual studio 10.0\vc\include\cmath    32  33 
33  IntelliSense: the global scope has no "llabs"   c:\program files (x86)\microsoft visual studio 10.0\vc\include\cstdlib  34  13 
34  IntelliSense: the global scope has no "lldiv"   c:\program files (x86)\microsoft visual studio 10.0\vc\include\cstdlib  34  32 
32  IntelliSense: the global scope has no "lldiv_t" c:\program files (x86)\microsoft visual studio 10.0\vc\include\cstdlib  32  13 
19  IntelliSense: the global scope has no "log10l"  c:\program files (x86)\microsoft visual studio 10.0\vc\include\cmath    33  13 
18  IntelliSense: the global scope has no "logl"    c:\program files (x86)\microsoft visual studio 10.0\vc\include\cmath    32  53 
27  IntelliSense: the global scope has no "mblen"   c:\program files (x86)\microsoft visual studio 10.0\vc\include\cstdlib  26  13 
28  IntelliSense: the global scope has no "mbstowcs"    c:\program files (x86)\microsoft visual studio 10.0\vc\include\cstdlib  26  32 
29  IntelliSense: the global scope has no "mbtowc"  c:\program files (x86)\microsoft visual studio 10.0\vc\include\cstdlib  26  54 
20  IntelliSense: the global scope has no "modfl"   c:\program files (x86)\microsoft visual studio 10.0\vc\include\cmath    33  33 
21  IntelliSense: the global scope has no "powl"    c:\program files (x86)\microsoft visual studio 10.0\vc\include\cmath    33  52 
23  IntelliSense: the global scope has no "sinhl"   c:\program files (x86)\microsoft visual studio 10.0\vc\include\cmath    34  31 
22  IntelliSense: the global scope has no "sinl"    c:\program files (x86)\microsoft visual studio 10.0\vc\include\cmath    34  13 
24  IntelliSense: the global scope has no "sqrtl"   c:\program files (x86)\microsoft visual studio 10.0\vc\include\cmath    34  50 
26  IntelliSense: the global scope has no "tanhl"   c:\program files (x86)\microsoft visual studio 10.0\vc\include\cmath    35  31 
25  IntelliSense: the global scope has no "tanl"    c:\program files (x86)\microsoft visual studio 10.0\vc\include\cmath    35  13 
30  IntelliSense: the global scope has no "wcstombs"    c:\program files (x86)\microsoft visual studio 10.0\vc\include\cstdlib  30  13 
31  IntelliSense: the global scope has no "wctomb"  c:\program files (x86)\microsoft visual studio 10.0\vc\include\cstdlib  30  35
Title: Re: Implementing Pairing Based Crypto on arduino uno
Post by: MarkT on May 16, 2018, 03:41 pm
It won't fit on a tiny microcontroller with 2k of SRAM.  (without miraculous coding skills!)
Title: Re: Implementing Pairing Based Crypto on arduino uno
Post by: simsam on May 17, 2018, 02:01 pm
It won't fit on a tiny microcontroller with 2k of SRAM.  (without miraculous coding skills!)
Thanks for replying.
Is there any way to increase the SRAM?

I only want to run the signature generation part of the PBC code on arduino. The verification part will be run on my server.
Title: Re: Implementing Pairing Based Crypto on arduino uno
Post by: MarkT on May 17, 2018, 02:06 pm
Use a bigger microcontroller - first you need to find out what memory / code space is needed for that
library - perhaps compile for something else and look at verbose compiler/linker output.

I suspect you're definitely in 32 bit processor, 100MHz+ territory.

What are you trying to secure?
Title: Re: Implementing Pairing Based Crypto on arduino uno
Post by: gfvalvo on May 17, 2018, 02:08 pm
Have you looked at a Teensy? (https://www.pjrc.com/teensy/)
Title: Re: Implementing Pairing Based Crypto on arduino uno
Post by: simsam on May 17, 2018, 02:10 pm
I am reading data of a sensor. And i want to attach a digital signature to it before sending it off to my server. For this i used PBC.

I got alot of errors when i compiled the code as pasted above.
Title: Re: Implementing Pairing Based Crypto on arduino uno
Post by: simsam on May 17, 2018, 02:18 pm
Have you looked at a Teensy? (https://www.pjrc.com/teensy/)
No i have not, I'll give it a look.
Thank you
Title: Re: Implementing Pairing Based Crypto on arduino uno
Post by: MarkT on May 17, 2018, 03:39 pm
I am reading data of a sensor. And i want to attach a digital signature to it before sending it off to my server. For this i used PBC.

I got alot of errors when i compiled the code as pasted above.
A digital signature is not the right primitive I think - a simple MAC is how to authenticate messages to a server.
Title: Re: Implementing Pairing Based Crypto on arduino uno
Post by: simsam on May 17, 2018, 05:03 pm
A digital signature is not the right primitive I think - a simple MAC is how to authenticate messages to a server.
Yes you are right a MAC will be enough for authentication, but it is a requirement of my project to use digital signatures.
This is mainly to ensure data integrity, and to prevent any tampering of data.
Whatever data is collected by the sensors it must be signed and then transmitted.
Title: Re: Implementing Pairing Based Crypto on arduino uno
Post by: MarkT on May 17, 2018, 05:37 pm
Quote
This is mainly to ensure data integrity, and to prevent any tampering of data.
In what way does a MAC not perform this task?  A signature binds a person to a document, that's
rather different.  (Well it need not be a person, its usually a certification authority).

A requirement is not the same thing as a technique.  The requirement is to prevent tampering,
not the technique chosen to satisfy the requirement.  Sounds like you've been ordered to
do something a particular way, not given a set of functional requirements!

Asymmetric crypto with public key management infrastructure is much more heavyweight than
shared-secret crypto, and is not normally doable on a tiny microcontroller.  Yes, that means
a microcontroller is more limited in its options, and that you'd better have distinct shared
secrets for each client.
Title: Re: Implementing Pairing Based Crypto on arduino uno
Post by: simsam on May 17, 2018, 08:17 pm
A requirement is not the same thing as a technique.  The requirement is to prevent tampering,
not the technique chosen to satisfy the requirement.  Sounds like you've been ordered to
do something a particular way, not given a set of functional requirements!

Sorry i think i didnt use the correct word, i should have used technique instead of requirement.
Though what you're saying is absolutely correct, the thing is that my supervisor has told me to use PBC here, i cant use an alternative.


Asymmetric crypto with public key management infrastructure is much more heavyweight than
shared-secret crypto, and is not normally doable on a tiny microcontroller.  Yes, that means
a microcontroller is more limited in its options, and that you'd better have distinct shared
secrets for each client.
Yes i understand that asymmetric crypto is more heavy weight, is there no way to implement this at all? What if i were to change from UNO to MEGA? Even that wouldnt suffice?
Title: Re: Implementing Pairing Based Crypto on arduino uno
Post by: simsam on May 17, 2018, 08:22 pm
Also, is the memory limitations a major issue here or the computational capabilities of the microcontroller?  I read in an article that a SD card may be used to increase the SRAM. Is that possible?
Title: Re: Implementing Pairing Based Crypto on arduino uno
Post by: gfvalvo on May 17, 2018, 08:26 pm
Also, is the memory limitations a major issue here or the computational capabilities of the microcontroller?  I read in an article that a SD card may be used to increase the SRAM. Is that possible?
Why would you even consider such extremes just to stay with an 8-bit processor? It's already been suggested (twice) that you move to a 32-bit machine.
Title: Re: Implementing Pairing Based Crypto on arduino uno
Post by: simsam on May 17, 2018, 10:59 pm
Why would you even consider such extremes just to stay with an 8-bit processor? It's already been suggested (twice) that you move to a 32-bit machine.
I looked it up and found arduino Due, it has a 32-bit processor.
Should i go ahead and buy it if this code will execute on it.
Title: Re: Implementing Pairing Based Crypto on arduino uno
Post by: MorganS on May 17, 2018, 11:35 pm
So, check if the code fits by looking at it. Does it assign any large buffers? How big are they?

Program storage is unlikely to be the issue, so you don't need to know how may bytes the program itself takes, just its SRAM storage while it's running.
Title: Re: Implementing Pairing Based Crypto on arduino uno
Post by: Coding Badly on May 17, 2018, 11:39 pm
Program storage is unlikely to be the issue...
Probably should at least glance at the on-disk size of the two libraries before claiming "unlikely".   ;)

Title: Re: Implementing Pairing Based Crypto on arduino uno
Post by: simsam on May 18, 2018, 12:49 am
So, check if the code fits by looking at it. Does it assign any large buffers? How big are they?

Program storage is unlikely to be the issue, so you don't need to know how may bytes the program itself takes, just its SRAM storage while it's running.
Yes it does assign large buffers, there is a large string i was provided which is used in generating the private key, around 400 character long.

Should i switch boards to arduino due instead? Or someone other board.

I dont have much knowledge regarding this so i need some help in deciding.
As mentioned in the earlier comments a 32 bit processor is required so i looked up DUE
Title: Re: Implementing Pairing Based Crypto on arduino uno
Post by: MorganS on May 18, 2018, 01:07 am
Probably should at least glance at the on-disk size of the two libraries before claiming "unlikely".   ;)


What does that tell you about a large crypto library that the Arduino side only needs to compile and link a few functions to do the 'signing'' side of the transaction?  You may as well look at the size of the math.h library on disk and claim that won't fit on an Arduino.

Simsam: the internal storage of the core cryptography is probably many times larger than the key. It will teach you a lot by going through the code to find out what functions it actually uses and what storage they use. It is entirely possible that it assigns static buffers for the decryption routines that you aren't even going to use on the Arduino.
Title: Re: Implementing Pairing Based Crypto on arduino uno
Post by: Coding Badly on May 18, 2018, 01:50 am
What does that tell you about a large crypto library that the Arduino side only needs to compile and link a few functions to do the 'signing'' side of the transaction?
A few functions.  How quaint.

Quote
You may as well look at the size of the math.h library on disk and claim that won't fit on an Arduino.
When elliptic curve functions have been added to "math.h" let me know.  Until then that is a false analogy.

But, there is no point discussing hypothetical with you when there is a trivial practical path to follow...

I have implemented Digital Signature using PBC   (https://crypto.stanford.edu/pbc/manual/ch01.html) and GMP libraries.( I have taken the code from the PBC library as liked above.)My code works correctly when i compile it on Visual Studios 2010.
Post the MAP file.  Armed with that it will be possible to assess the size processor.

Title: Re: Implementing Pairing Based Crypto on arduino uno
Post by: simsam on May 18, 2018, 01:21 pm
A few functions.  How quaint.


Post the MAP file.  Armed with that it will be possible to assess the size processor.

I have attached the map file.
Title: Re: Implementing Pairing Based Crypto on arduino uno
Post by: MarkT on May 18, 2018, 01:37 pm
Sorry i think i didnt use the correct word, i should have used technique instead of requirement.
Though what you're saying is absolutely correct, the thing is that my supervisor has told me to use PBC here, i cant use an alternative.


Yes i understand that asymmetric crypto is more heavy weight, is there no way to implement this at all? What if i were to change from UNO to MEGA? Even that wouldnt suffice?
No, its ~ 10000 times slower than stock computer hardware, its an 8-bit microcontroller.

We are talking 3 to 5 orders of magnitude difference in performance, basically, between a
small micricontroller and a general purpose processor, considering memory, speed or transistor count.

For a small microcontroller an efficient block-cipher based MAC is feasible, asymmetric crypto systems are not.

Even on the Due or similar with 32 bit architecture you'll find the performance is dissappointingly slow, and
typically you'd only use asymmetric crypto to set up a secure channel using standard symmetric crypto, so that the heavyweight step only
has to happen once (or perhaps once per day or similar).  I recommend reading "Cryptography Engineering: Design Principles and Practical Applications" by Ferguson/Schneier/Kohno.
Title: Re: Implementing Pairing Based Crypto on arduino uno
Post by: simsam on May 18, 2018, 02:17 pm
No, its ~ 10000 times slower than stock computer hardware, its an 8-bit microcontroller.


For a small microcontroller an efficient block-cipher based MAC is feasible, asymmetric crypto systems are not.

Even on the Due or similar with 32 bit architecture you'll find the performance is dissappointingly slow, and
typically you'd only use asymmetric crypto to set up a secure channel using standard symmetric crypto, so that the heavyweight step only
has to happen once (or perhaps once per day or similar).  I recommend reading "Cryptography Engineering: Design Principles and Practical Applications" by Ferguson/Schneier/Kohno.

Thank you for your detailed answer. I will discuss this with my supervisor.
So the conclusion being that running an asymmetric crypto (PBC) will not be possible on any arduino board. I will have to move to something else.
Thank you again for your help.
Title: Re: Implementing Pairing Based Crypto on arduino uno
Post by: gfvalvo on May 18, 2018, 02:43 pm
So the conclusion being that running an asymmetric crypto (PBC) will not be possible on any arduino board.
If you're really interested, I'd say get a Teensy 3.6 (https://www.pjrc.com/store/teensy36.html) (32-Bit ARM Cortex-M4, 180/360 MHz, 256 KB RAM, 1 MB Program Space) and give it a try. It will set you back all of $30.
Title: Re: Implementing Pairing Based Crypto on arduino uno
Post by: simsam on May 18, 2018, 07:40 pm
If you're really interested, I'd say get a Teensy 3.6 (https://www.pjrc.com/store/teensy36.html) (32-Bit ARM Cortex-M4, 180/360 MHz, 256 KB RAM, 1 MB Program Space) and give it a try. It will set you back all of $30.
Alright i will give that a try as well, using a digital signature is a key factor in the project i am given. So anything that'll make it work i'm up for it.
Thank you for helping me out.
Title: Re: Implementing Pairing Based Crypto on arduino uno
Post by: Coding Badly on May 19, 2018, 02:57 am
I have attached the map file.
sha.obj is the only module bound to the executable: 1953 bytes (Pentium class processor).  There are at least three SHA implementations for AVR processors so it is not too surprising that something named "sha" would be small enough to fit in an Uno's memory.  The rest (memory management, pbc, and floating-point) is dynamically linked.

The program uses structured exceptions which will be troublesome in the best case and non-existent in the worst case.  I believe the libraries are "pure C" in which case structured exceptions can be easily managed / avoided.

Title: Re: Implementing Pairing Based Crypto on arduino uno
Post by: simsam on May 19, 2018, 10:07 pm

The program uses structured exceptions which will be troublesome in the best case and non-existent in the worst case.  I believe the libraries are "pure C" in which case structured exceptions can be easily managed / avoided.


Yes the libraries are pure C, could be please elaborate a little that what do you mean by structured exceptions.

When the code was compiles visual micro, there were a lot of errors regarding the cmath library, none of its functions were being recognized.

Should i also attach the code?
Title: Re: Implementing Pairing Based Crypto on arduino uno
Post by: Coding Badly on May 19, 2018, 10:28 pm
Yes the libraries are pure C, could be please elaborate a little that what do you mean by structured exceptions.
try ... catch

In your case that gets broadened to include Microsoft extensions...
https://www.google.com/search?q=c%2B%2B+structured+exception+handling (https://www.google.com/search?q=c%2B%2B+structured+exception+handling)

Title: Re: Implementing Pairing Based Crypto on arduino uno
Post by: Coding Badly on May 19, 2018, 10:37 pm
Should i also attach the code?
I suggest you create a test program that builds for an Arduino using stubs for the PBC calls.  Then get that to build and run correctly on a PC.  Doing that will eliminate most / all of the PC specific junk (like basic_string) and give you a starting point for building something that works correctly on an Arduino.