Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I'm going to assume this isn't possible, but I have to ask because I'm trying to fundamentally understand what I've thus far been trying to implement by following an RFC.

SRP-6a starts off with declaring that I should choose $N$, a sufficiently large prime, and $g$, a generator. Let's say $N$ is 1024-bits and $g$ is 2. A sufficiently random number $a$ is generated. For arguments sake I chose the length of $a$ to be 128 bits. My public key $A$ is then given as $g^a \bmod N$.

Now, assume that I'm the server (or in this case I'm just trying to debug an SRP-6a protocol), and I receive $A$. Since I know both $g$ and $N$, can I determine $a$ (in a reasonable amount of time). I'm guessing absolutely not, but it would be nice to know precisely why.

share|improve this question

1 Answer 1

up vote 4 down vote accepted

When using a Discrete Logarithm based scheme, such as SRP, the rule of thumb is to always use private exponents with a bit length twice the desired security strength. Hence, a 128 bit exponent $a$ will at most give you 64 bits of security. If you want 128 bit security, you need (at least) a 256 bit exponent. This is because the algebraic structure of the groups used for such schemes, make it possible to calculate discrete algorithms using a meet-in-the-middle approach that effectively halves the necessary effort, compared to a naive brute force approach.

In this case, for instance, let $q$ be the order of $g$ in $\mathbb Z_N$. Calculate $y = A(g^{q-x2^n}) \bmod N$ for all $0 \le x \lt 2^{128-n}$ and put the pairs $y,x$ in a table for fast access, indexed by the $y$ component. Next calculate $y' = g^z \bmod N$ for all $0 \le z \lt 2^n$. If you find a $y$ in the table such that $y = y'$, then you know that $z = a - x2^n \bmod q$, and hence that $a = z + x2^n$.

The latter calculations might be carried out in parallel and might be more effectively optimized than the former, so the optimal trade-off might e.g. be to set $n = 80$, meaning you put $2^{48}$ pairs $y,x$ in your table and perform a total of $2^{80}$ parallel calculations $y' = g^z \mod N$. This is feasible using modern hardware.

share|improve this answer
    
You lost me with $q$. To simplify things I have chosen $N=251$, $g=2$ (though I am confused as to what a generator is anyway), and $a=43$. That gives me $A=2^{43} \bmod N = 151$. Where would $q$ fit in? In this example is $\mathbb Z_{251}$ known as the group $G$? –  Joe Aug 9 at 15:04
    
You also introduce $n$, what is that? –  Joe Aug 9 at 15:10
    
@Joe In SRP, $g$ is supposed to be a generator of the multiplicative group, meaning that the order of $g$ should be $q = N-1$. Since $N$ is supposed to be a safe prime, the only other possible values are $q = (N-1)/2$, $q = 2$ and $q = 1$. Checking the order of $g$ is done by finding the least $q$ such that $g = g^q \bmod N$. –  Henrick Hellström Aug 9 at 15:53
    
The parameter $n$ in my answer is an arbitrary attack parameter that might be any value between $0$ and $128$. –  Henrick Hellström Aug 9 at 15:56
    
Thanks @Henrick, I'm clearly still learning, a trip to the bookstore is in order. In my above comment about $g = 2$, I've just figured that it cannot be if $N = 251$, but $6$ can. If I'm now understanding generators correctly. –  Joe Aug 9 at 16:00

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.