Re: swc / ActivCard

[Michal Zalewski <lcamtuf () DIONE IDS PL>]

On Wed, 23 Aug 2000, Alan DeKok wrote:

> A simple check of the 106 6-digit numbers shows that 33 are less
> than 5x10^5.  For random numbers, you'd expect a number closer to 53.
> I won't bother doing the math to discover the probability of 33/106
> happening by chance, but I'd guess it to be somewhat low.

It is. There are also other, already discussed things - like higher /
lower probabilities of some sequences in binary representation, long block
of even numbers, some ranges "preferred" more often than others... All of
this can happen by chance, that's why I asked other people to verify if
they can see such long-term effects like this "broken symmetry".

But this discussion is senseless when talking constantly about the same
input set of 106 numbers. That's why I didn't wanted to post detailed
analysis of this sequence, because all of my observations can be
accidental. Only feedback from other AC users, saying they confirmed such
problems or didn't noticed them can be usable.

And only then we can say: AC is buggy or AC is good. I stated it in my
original post.

>   That is, *if* that sequence did come from an ActivCard token.

It did.

> No, you said that you could *predict* the numbers with 35% accuracy.
> That statement is a LOT stronger than noting statistical
> irregularities with the output of DES operations.  Please don't change
> your story.

I just want to say it's possible to derive function that will fit this
data in 100%, but won't be usable outside this data set. Yes, it is
possible, ALWAYS. I tried to find some generic - at least for this card -
rules (like higher / lower than expected probability of some sequences)
for prediction, and (again, at least for this card) I was able to
recognise some IMHO not exactly random patterns to rise the probability of
my guesses from expected probability - 1 / 100000000 - to something around
1 / 200 to 1 / 1000 in most cases. But I'm not sure if I found a rule only
for my input set and this (maybe specific) token, or AC algorithm is
somewhat weaker than we should expect?

Also, I didn't even mention DES - I'm not saying DES is weak. I only
suspect the moment when DES output is used to construct decimal numbers.

> Any statistical issues might be minor, as you only supplied ~100
> numbers.  Maybe if we looked at 10,000 numbers, the irregularities
> might go away.

That's why I asked other people to support me and verify this information.

> Personally, I would like you to supply *all* of the information you
> used to make that 35% prediction.

Most of it has been attached. I've collected another probe about the same
length, plus did some not-recorded down attempts. Unfortunately, I'm
having real problems for publishing this sequence already (mainly because
I wasn't the owner of this tokens, nor I didn't get permission from AC).

I don't want to do that, anyway. Because it won't change anything. I guess
people should test THEIR configurations, and check THEIR tokens, to find
if problem doesn't persist at all, or only in specific situations - or
maybe, it's present always on ActivCard One synchronous tokens.

That's it. I posted (brief) description of things I've done, and brief
description of problem I've noticed. But I didn't do that to start
speculations about this specific case, but to VERIFY IF THIS PROBLEM IS
MORE GENERAL, OR RELATED TO THIS TOKEN ONLY. Or maybe to find if I'm wrong
and this data is purely random / unpredictable.

Up to 35% in 100 attempts is real result, but it's not the matter of _my_
results, but matter of results obtained by other people. And not results
of specific tool, but results of basical analysis. Using methods we
already discussed in this thread. As far, I get some valuable comments,
some flames, but didn't get _ANY_ attempt to perform independent tests or
even portions of data collected independently.

_______________________________________________________
Michal Zalewski [lcamtuf () tpi pl] [tp.internet/security]
[http://lcamtuf.na.export.pl] <=--=> bash$ :(){ :|:&};:
=-----=> God is real, unless declared integer. <=-----=