OPENSSL_ia32_rdrand cmp/cmove instructions

Question

I am trying to understand the x86 assembly function used in OpenSSL to get random bytes using the CPU's RDRAND instruction. Here is the function body:

OPENSSL_ia32_rdrand:
    mov     $8,%ecx
.Loop_rdrand:
    rdrand  %rax
    jc      .Lbreak_rdrand
    loop    .Loop_rdrand
.Lbreak_rdrand:
    cmp     $0,%rax
    cmove   %rcx,%rax
    ret

I can't figure out the purpose the the cmp and cmove instructions. I am not an x86 assembly programmer, but from what I can tell from the references that I've looked at, my understanding of what it's doing is:

10 load retry counter to ecx
20 get random number into rax
30 if successful (carry flag set) goto 50
40 decrement counter and goto 20 if not zero
50 check if rax is zero
60 if it is, move rcx to rax
70 return

So, rax can only be 0 if rdrand failed (carry flag is clear), and the cmp instruction can only be reached if either 1) rdrand succeeded (carry set) and put a non-zero number in rax, or 2) the retry counter in ecx has been decremented to 0. In case 1, the cmp fails and cmove does not execute the move. In case 2, rcx contains 0 and cmove moves 0 to 0. Either way the cmove is a no-op.

Am I misunderstanding what one or more of the assembly instructions do?

Good catch and good question. The OpenSSL project has a really sharp fellow who does this stuff, so it will be interesting to see his reasoning. — jww, Apr 30 '14 at 05:31

score 3 · Answer 1 · answered Apr 29 '14 at 11:47

3

You have a slight misunderstanding.

You got the main part right, there are 8 attempts to retrieve random number using RDRAND but CMOVE isn't necessarily NOP if RDRAND returned 0 as random number. In that case this function will return value of the RCX (Loop count) as 'random number'. In short, this function will only return 0 when no random number was available - otherwise it'll return real random number from RDRAND or iteration number on which you received the 0 from RDRAND.

answered Apr 29 '14 at 11:47

vhu

12,244
11
38
48

3

I didn't think that was possible. The Intel reference I was looking at states that when CF=1, "Destination register valid. _Non-zero_ random value available at time of execution." (Emphasis mine.) After doing a little more research, it appears that it only applies to early versions of the CPU. Current ones can indeed return a random zero, as they should. I suspect the decision to return the retry counter instead of 0 is because OpenSSL's API was already established to use that to signal error, but I'm just speculating. Still, random number function that can't return 0 just seems plain wrong. – user128469 Apr 30 '14 at 02:36

EOF · Answer 2 · 2014-04-29T20:01:13.850

1

It's not just you who has a slight misunderstanding. Whoever programmed this didn't know what they were doing (hmm, OpenSSL you say... What a surprise). Intel's software developer's manuals recommend:

#define SUCCESS 1
#define RETRY_LIMIT_EXCEEDED 0
#define RETRY_LIMIT 10

int get_random_64( unsigned __int 64 * arand)
{
int i ;
for ( i = 0; i < RETRY_LIMIT; i ++)
    {
        if(_rdrand64_step(arand) ) return SUCCESS;
    }
return RETRY_LIMIT_EXCEEDED;
}

After some slight changes to get it to compile on gcc, I get:

get_random_64:
    movl    $10, %edx
    movl    $1, %ecx

.L3:
    rdrand  %rax
    movq    %rax, (%rdi)
    cmovb   %ecx, %eax
    testl   %eax, %eax
    jne .L4
    subq    $1, %rdx
    jne .L3
    rep ret
.L4:
    movl    $1, %eax
    ret

This will actually return a zero when rdrand() randomly produces it, instead of returning a small nonzero integer in that case. I'd say a random function that can't return zero and has a slightly increased probability to return an integer between one and eight is defective by design, since its output is biased.

edited Apr 29 '14 at 20:01

answered Apr 29 '14 at 19:55

EOF

6,273
2
26
50

Well, the code may be trying to avoid a catastrophic failure so that a string of all 0's is not returned to a caller. But even a value in the range of `[1 -8]` seems like a catastrophic failure to me. Its hard to tell since there are no comments to explain the reasoning. What is clear: the API appears broken since it *cannot* convey success/failure. The caller will always march on as if successful. – jww Apr 29 '14 at 23:01
2

To be fair, OPENSSL_ia32_rdrand *can* convey failure by returning 0. It just can't return a random 0, which I agree is a broken API. – user128469 Apr 30 '14 at 02:34
Oh, OK. So `RAX` is 64 bits, which means the function can return `2^64 - 1` values (rather than the full `2^64`). I can't imagine a adversary gaining an advantage with it. It would have been nice if the code was commented as such. – jww Apr 30 '14 at 05:50
1

@user128469 Well, the most probable case for returning zero in the openSSL version is a hardware defect, in which case *all* numbers returned by the function will be zero. I'm not impressed. I agree that not returning a random zero is not a severe problem, but the bias for 1-8 *is*. – EOF May 01 '14 at 04:24

OPENSSL_ia32_rdrand cmp/cmove instructions

2 Answers2

Linked