John Payson wrote:
>
> I was thinking of the RAM limit (the 12Cc5xx has 25 bytes, whereas the
> 16F84 has 68 RAM + 64 EEPROM).
>

   The 12C509 has 1K of code and 41 bytes of RAM so that should be
enough for what I'm doing.  Again I hope.  Actually, I'm pretty sure.
I'm not trying to guard our national security with this thing.  All
I want is to make any would be thieves work if they really want
my *not new* car.  :-)  Quoting the other replier, there're many
more primative ways to break into a car beside breaking my code. :-)


>
> Suppose you want a unit to be 'good for' 65,536 activations (I think in
> practice 1,000,000 would be a better target).  This means the first time
> you push the button you'd have to compute h[65536], the next time you'd
> compute h[65534], etc.  Unfortunately, computing h[65536] directly would
> take rather a long time (if the hash takes 10ms, then h[65536] would take
> over 10 minutes).  On the other hand, h[65536] could be computed in only
> 160ms given h[65520] (just run the hash 16 more times).  If the system
> kept a copy of h[65520] it could compute any of h[65520..65535] with 16 or
> fewer hash operations.  Unfortunately, when the system reached h[65519] it
> would have a problem unless there was some convenient lower target
> available.
>


   The obvious question is why must the hash be ran in a descending
order?  Does running the hash in an ascending order jeopordizes
the security of h[]?


> While the "nicest" method of implementing the h[] function in the
> transmitter would be to compute all the values h[1] to h[65536] and store
> them in a table somewhere, this is unfortunately not practical given the
> memory constraints of the PIC.  It is possible, however, to do reasonably
> well with a small amount of memory; 65536 keys can be output in reverse
> order using only 4 keys' worth of RAM and no more than 60 calls to the
> hash function for any key.  Expanding the domain of h[] to accomodate
> 2^20 keys would only require increasing RAM to 5 keys' worth and the
> number of hash-calls per key to 80 (*).  To illustrate the method, I'll
> shrink the domain to 256.
>

   I'm supposing that the 4 keys requirement you described was
factored into consideration the background computation of far off
keys?  Because 65536/4 > 10000 so each key would need a maximum of
more than 10000 calls to h[].  How did the figure of 4 keys and
no more than 60 calls came up?


> (*) There are tradeoffs between the amount of RAM and the number of
> computations.  At one extreme is having 65536 keys in RAM; then no
> computations are required for any of 'em.  At the other extreme is having
> one key in RAM and having to do up to 65536 computations on it.  For a
> 16F84 implementation using 40-bit keys and a 2^20 domain, having 5 keys in
> memory is probably reasonable [25 bytes]; if the number of keys' worth of
> memory were increased to 10, then only 24 calls to the hash function would
> be needed per key.


   If all computers come with unlimited amount of RAM, then Computer
Science wouldn't be as interesting as it is now.  :-)  I still don't
understand how you arrive at the number of keys and number calls
figure.  Would you like to expand on that?.


>
> Suppose we start out knowing h[240] and needing to compute h[255].  This
> will take us 15 steps.  The next time we need to compute a hash, its value
> will be h[254] and it will take 14 steps.  The problem will come when we
> get below 240; we'll encode 16 times before we have that problem and we'll
> want to compute h[224].  The key observation here is that while computing
> h[224] will take 224 steps, we can do a little bit of the work on each of
> the transmissions we'll have before we need h[224].  Consequently, each
> transmission value can be produced in less than 30 cycles total [15 max to
> find the 'base', and 15 max to go from the base to the final value].
>
> While I don't know how long it would take a 16F84 to compute a DES-style
> hash, the computations involved with a one-way-hash transmitter should be
> quite reasonable.  While it may take many hours of CPU time to compute
> some of the larger hashes, those hours of CPU time could be spread out
> over the thousands of transmit-requests that would be processed before the
> large hashes would be needed.  Does anyone know what if any patents such
> methods might fall afoul of?


Andy
------------
bikejog@bellatlantic.net
http://www.mcs.drexel.edu/~uachang