Creating a lookup table with 30,000 Date and char[5] key value pairs

Troubleshooting
1

I have 30,000 rows of key,value pairs consisting of a date and a 5 character token. Each date and token are unique, meaning there are no duplicate dates or tokens in the entire data set. Here is a sample:

date Token
2017-03-30 1465C
2017-03-31 223CF
2017-04-01 474E9
2017-04-02 584E1
2017-04-03 12497
2017-04-04 BB9DB
2017-04-05 05EF0

The routine I want to write: bool validateToken(const char* tkn) determines if the token provided matches the token associated with TODAYS date.

I believe the best container has the type std::map<time_t, char[5]> and was going to write a data structure in that format with all that data.

I was just given the data, but generally I think the tokens are all hex values and range between: 0x00000 - 0xFFFFF

I’m looking for a fast solution that uses a small memory space. What is the best approach to this?

Do I use PROGMEM to store this data in flash?

What if I wrote 30,000 rows of #define TOKEN_1465C <relevantunix_time_stamp> then did comparisons with todays date?

There is no hash function and a lookup table is the only way I have to do it.

2

Hi @rama

First off if the dates are sequential as shown, you don’t need to store them–just use todays date minus a starting date as the index into an array.

The problem is the 5 character hex string, which represents a 20-bit value. You need to store 30,000 of these and they will take 4 bytes each, so that is 120,000 bytes of Flash memory, which is quite a bit but still might fit if your program is simple. The best way to store these is just to declare a global const array with the values as int. Const global ensures that the array ends up in Flash and not copied to RAM. You do not need the Arduino PROGMEM directive on Particle but is doesn’t hurt anything–it is just a no-op.

I would not use std::map since that will be heap allocated and there is not enough RAM to do that, plus you need them in flash anyway to initialize the map.

By the way, 30,000 of these at one per day is a little over 82 years worth, which is probably outside the useful life of this device.

I don’t understand your last comment about a hash function completely, but if the values are a hash of the date string, then you don’t need a table at all. You would just need to program the hash function into the device and construct today’s date as a string (easy) and then hash it to see if it matched the token.

If this is some sort of dongle for protection of software or a lock or similar, I would heartily recommend against this approach to security! Even if the hash function is secret, this is suseptable to lots of spoofing or replay attacks and is not secure.

3

Hi @bko,

The const array makes sense; that will be used. I obviously won’t put in 30,000 elements of sequential dates but it was just for general knowledge in case I have a situation that actually requires storing 30,000 unique elements.

Your paragraph on using a hash function correctly interpreted what I was saying. If there was a hash function to convert a date to a token then I wouldn’t need any sort of storage on board.

I agree on the security issue. The device will process SMS messages with commands to retrieve data from a remote modbus device.

My initial security measure was to retrieve authorized phone numbers via a webhook and only authorized numbers would receive responses from the device ie. if you’re not on the list no device response would be given for any case.

The device is for a client of mine and they want authorization in the form:

getdata [token]

Where anyone can SMS the device if they have the right token then they get a valid response. The token will change based on the day.

Do you have any recommendations on a better and more secure approach? Offering a suggestion by a security expert could offer more credibility :slight_smile: