PSSR (RSA) Metrics

[Jeffrey Walton]

Hi All,

I wanted to toss the following out in case others grepped for it on
the group. I know Wei had addressed it previously.

PSSR does not appear to be a viable solution for _hand keying_ a
Signature with Recovery (an example application would be a product
key). The ciphertext appears to be too large.

Security levels not withstanding, here are some figures and results

256 bit curve:
PK_Signer: key too short for this signature scheme
384 bit curve:
Messages of 1 to 4 bytes: length of 54 bytes (approximately 85
Base32 Encoded digits)
Message of 6 bytes: TF_SignerBase: the recoverable message part is
too long for the given key and algorithm

[Jens Peter Secher]

On 1/4/07, Jeffrey Walton <nolo...@gmail.com> wrote:

> PSSR does not appear to be a viable solution for _hand keying_ a
> Signature with Recovery (an example application would be a product
> key). The ciphertext appears to be too large.

I have in the past used a modified MD5 (called MD5Quart) which only
used 32 bit of the MD5 hash. I have include the diff to the real MD5
below. When I use this new hash as in

CryptoPP::RabinSS< CryptoPP::PSSR, CryptoPP::MD5Quart >::Signer privateKey
CryptoPP::RabinSS< CryptoPP::PSSR, CryptoPP::MD5Quart >::Verifier recover

the overhead is 80 bit, which amount to 16 characters in a base-32
encoding.

diff -u "md5.h" "md5quart.h"
--- crypto/md5.h Mon Jun 16 12:02:30 2003
+++ crypto/md5quart.h Mon Jun 16 12:02:31 2003
@@ -1,22 +1,23 @@
-#ifndef CRYPTOPP_MD5_H
-#define CRYPTOPP_MD5_H
+#ifndef CRYPTOPP_MD5QUART_H
+#define CRYPTOPP_MD5QUART_H

#include "iterhash.h"

NAMESPACE_BEGIN(CryptoPP)

-//! <a href="http://www.weidai.com/scan-mirror/md.html#MD5">MD5</a>
-/*! 128 Bit Hash */
-class MD5 : public IteratedHashWithStaticTransform<word32,
LittleEndian, 64, MD5>
+/*! 32 bit hash */
+class MD5Quart : public IteratedHashWithStaticTransform<word32,
LittleEndian, 64, MD5Quart>
{
public:
- enum {DIGESTSIZE = 16};
- MD5() : IteratedHashWithStaticTransform<word32, LittleEndian, 64,
MD5>(DIGESTSIZE) {Init();}
+ enum {DIGESTSIZE = 4};
+ MD5Quart() : IteratedHashWithStaticTransform<word32, LittleEndian,
64, MD5Quart>(DIGESTSIZE) {Init();}
static void Transform(word32 *digest, const word32 *data);
- static const char * StaticAlgorithmName() {return "MD5";}
+ static const char * StaticAlgorithmName() {return "MD5Quart";}

protected:
void Init();
+private:
+ static word32 a, c, d;
};

NAMESPACE_END

diff -u "crypto/md5.cpp" "crypto/md5quart.cpp"
--- crypto/md5.cpp Mon Jun 16 12:02:30 2003
+++ crypto/md5quart.cpp Mon Jun 16 12:02:30 2003
@@ -1,28 +1,32 @@
-// md5.cpp - modified by Wei Dai from Colin Plumb's public domain md5.c
-// any modifications are placed in the public domain
+// md5quart.cpp - modified by Jens Peter Secher
+// from Wei Dai
+// from Colin Plumb's public domain md5.c

#include "pch.h"
-#include "md5.h"
+#include "md5quart.h"
#include "misc.h"

NAMESPACE_BEGIN(CryptoPP)

-void MD5_TestInstantiations()
+void MD5Quart_TestInstantiations()
{
- MD5 x;
+ MD5Quart x;
}

-void MD5::Init()
+word32 MD5Quart::a;
+word32 MD5Quart::c;
+word32 MD5Quart::d;
+
+void MD5Quart::Init()
{
- m_digest[0] = 0x67452301L;
- m_digest[1] = 0xefcdab89L;
- m_digest[2] = 0x98badcfeL;
- m_digest[3] = 0x10325476L;
+ a = 0x67452301L;
+ m_digest[0] = 0xefcdab89L;
+ c = 0x98badcfeL;
+ d = 0x10325476L;
}

-void MD5::Transform (word32 *digest, const word32 *in)
+void MD5Quart::Transform (word32 *digest, const word32 *in)
{
-// #define F1(x, y, z) (x & y | ~x & z)
#define F1(x, y, z) (z ^ (x & (y ^ z)))
#define F2(x, y, z) F1(z, x, y)
#define F3(x, y, z) (x ^ y ^ z)
@@ -31,12 +35,9 @@
#define MD5STEP(f, w, x, y, z, data, s) \
w = rotlFixed(w + f(x, y, z) + data, s) + x

- word32 a, b, c, d;
+ word32 b;

- a=digest[0];
- b=digest[1];
- c=digest[2];
- d=digest[3];
+ b=digest[0];

MD5STEP(F1, a, b, c, d, in[0] + 0xd76aa478, 7);
MD5STEP(F1, d, a, b, c, in[1] + 0xe8c7b756, 12);
@@ -106,10 +107,10 @@
MD5STEP(F4, c, d, a, b, in[2] + 0x2ad7d2bb, 15);
MD5STEP(F4, b, c, d, a, in[9] + 0xeb86d391, 21);

- digest[0]+=a;
- digest[1]+=b;
- digest[2]+=c;
- digest[3]+=d;
+ a+=a;
+ digest[0]+=b;
+ c+=c;
+ d+=d;
}

NAMESPACE_END

--
Jens Peter Secher
_DD6A 05B0 174E BFB2 D4D9 B52E 0EE5 978A FE63 E8A1 jpsecher gmail com_
A. Because it breaks the logical sequence of discussion
Q. Why is top posting bad?