[FFmpeg-devel] [PATCH] DES en-/decryption

[Michael Niedermayer]

Hi

On Sat, Oct 13, 2007 at 10:15:42PM +0200, Reimar D?ffinger wrote:
> Hello,
> some DES implementation is needed for asf decryption support.
> This version, compared to the one contained in the previous asf patch,
> should be quite a bit faster (not benchmarked though).
> If you think this is not optimized well enough to belong in libavutil I
> tend to suggest to leave it in libavformat unless someone else is
> interested in improving it.
> I am interested in hearing your comments either way.
> Btw.: this code would allow for the S_boxes_P_shuffle table to be
> generated at compile time, which is an approach I would greatly prefer,
> but I don't know how to implement this in a non-messy way.
> If any of the "Makefile-guys" have some time, maybe you could see if you
> can come up with something? I'd expect this could be used in some other
> code as well (I hope others agree this would be nice).

[...]
> +static uint32_t f_func(uint32_t r, uint64_t k) {
> +    int i;
> +    uint32_t out = 0;
> +    // expand 32 bit data to 8 * 6 bit blocks
> +    uint64_t tmp = shuffle(r, E_shuffle, sizeof(E_shuffle));
> +    tmp ^= k;
> +    // apply S-boxes, those compress the data again from 8 * 6 to 8 * 4 bits
> +#ifdef CONFIG_SMALL
> +    for (i = 0; i < 8; i++) {
> +        uint32_t v = S_boxes[i][(tmp >> 43) & 0x1f];
> +        if (tmp & ((uint64_t)1 << 42)) v >>= 4;
> +        else v &= 0x0f;
> +        tmp <<= 6;
> +        out = (out << 4) | v;
> +    }
> +    out = shuffle(out, P_shuffle, sizeof(P_shuffle));
> +#else
> +    for (i = 7; i >= 0; i--) {
> +        out |= S_boxes_P_shuffle[i][tmp & 0x3f];
> +        tmp >>= 6;
> +    }
> +#endif

cant something like

for(){
    out |= S_boxes_P_shuffle[i][(tmp ^ k) & 0x3f];
    k >>= 6;
    tmp >>= 4;
}

be used to get rid of the E_shuffle?
this might be both faster and smaller

also aligning the expanded data so that >>=8 and (uint8_t)tmp could be
used might be faster

and then i think the output could be kept in expanded format which would
simplify that further but require a bigger table, so maybe this is not
such a good idea i dunno



> +    return out;
> +}
> +

> +/**
> + * \brief rotate the two halves of the expanded 56 bit key each 1 bit left
> + *
> + * Note: the specification calls this "shift", so I kept it although
> + * it is confusing.
> + */
> +static uint64_t key_shift_left(uint64_t CDn) {
> +    uint64_t carries = (CDn >> 27) & 0x10000001;
> +    CDn <<= 1;
> +    CDn &= ~0x10000001;
> +    CDn |= carries;
> +    return CDn;
> +}
> +
> +/**
> + * \brief rotate the two halves of the expanded 56 bit key each 1 bit right
> + *
> + * Note: the specification calls this "shift", so I kept it although
> + * it is confusing.
> + */
> +static uint64_t key_shift_right(uint64_t CDn) {
> +    uint64_t carries = (CDn & 0x10000001) << 27;
> +    CDn >>= 1;
> +    CDn &= ~(0x10000001ULL << 27);
> +    CDn |= carries;
> +    return CDn;
> +}

static uint64_t key_rotate(uint64_t CDn, int s, uint64_t m){
    return ((CDn >> s) & m) | ((CDn << s) & ~m);
}

or does this lead to a larger object file?




> +
> +uint64_t ff_des_encdec(uint64_t in, uint64_t key, int decrypt) {
> +    int i;
> +    // discard parity bits from key and shuffle it into C and D parts
> +    uint64_t CDn = shuffle(key, PC1_shuffle, sizeof(PC1_shuffle));
> +    // shuffle irrelevant to security but to ease hardware implementations
> +    in = shuffle(in, IP_shuffle, sizeof(IP_shuffle));
> +    for (i = 0; i < 16; i++) {
> +        uint64_t Kn;
> +        uint32_t f_res;
> +        if (!decrypt) {
> +            CDn = key_shift_left(CDn);
> +            if (i > 1 && i != 8 && i != 15)
> +                CDn = key_shift_left(CDn);
> +        }
> +        Kn = shuffle(CDn, PC2_shuffle, sizeof(PC2_shuffle));
> +        f_res = f_func(in, Kn);
> +        in = (in << 32) | (in >> 32);
> +        in ^= f_res;
> +        if (decrypt) {
> +            CDn = key_shift_right(CDn);
> +            if (i != 0 && i != 7 && i < 14)
> +                CDn = key_shift_right(CDn);
> +        }
> +    }

key_shift_right() could be avoided by storing the keys in a table (this could
even just be on the stack and done each time if you dont want a context)
next the shift could be merged with the PC2_shuffle
removing the need for a key_shift*

PS: if any suggestion i made makes no sense, maybe it really doesnt make
sense, iam no DES expert and i might have missed some things ...

[...]
-- 
Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB

Freedom in capitalist society always remains about the same as it was in
ancient Greek republics: Freedom for slave owners. -- Vladimir Lenin
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
URL: <http://lists.mplayerhq.hu/pipermail/ffmpeg-devel/attachments/20071013/203f0608/attachment.pgp>