Hi(Apologies for cross-posting, but the issue is pertaining to
implementers, which are more likely interested in the full OStatus
suite.)
Today I was pointed to a microblog entry[1] claiming that almost all
implementations of the RSASSA-PKCS1-v1_5 padding are broken. This is a
confirmation of my own experience, having unsuccessfully tried to
implement it both with OpenSSL[2] and manually[3].I propose a few things we could do about this:
* Decide whether to stick with real PKCS padding, or to keep the
different but already-implemented padding* Fix the examples in the Salmon protocol specification (known issue[4]
if you discover it after wondering why your own tests fail)* Appoint a reference (or known-to-work) implementation for developers
to test against. I was happy to have had a VM image w/ StatusNet from
FSW2011, but the OStatus plugin I tested against came with its own PHP
RSA implementation that hasn't been reviewed as much as OpenSSL has.
Hence, the potential location of errors isn't as narrow.
[1] http://macgirvin.com/display/mike/22042
[2] https://github.com/astro/node-ostatus/blob/dev-salmon/src/provenance.cc
[3] https://github.com/astro/node-ostatus/blob/dev-salmon-manual-emsa/src/provenance.cc
[4] http://code.google.com/p/salmon-protocol/issues/detail?id=8
Friendika has salmon interop with statusnet and minime, and I have some
basic Diaspora salmon inter communication working (there's a bit more
work before it's stable). There are several other implementations which
have achieved salmon interop with statusnet.
The point of my post which started this whole mess is that to achieve
interop with Diaspora, I discovered that all the existing statusnet
inter-operable implementations are non spec compliant in their low level
signatures. Diaspora does it differently than anybody else, but all are
technically broken, including my own.
[John - Was recently wondering about the choice of the word 'sign' on
step 6. I think technically at step 6 we're just encrypting the emsa
blob with the author's private key. But I may be missing something.]
> This makes things compatible with standard (Java, C) APIs for doing
> RSA public key signatures, so that a developer just doing the obvious
> thing gets the right results. Otherwise they have to actually drop
> down to lower level APIs and write crypto code.
Unfortunately, developers doing the "obvious" thing has led to the
current situation. The openssl sign/verify exposed to PHP and Ruby
doesn't have the emsa padding bytes. Neither does the PHPsec library -
which we have been using in PHP to deal with modulus/exponent keys.
Diaspora in fact uses exactly the same openssl sign/verify algorithm,
but with a different key format than that used with PHP openssl.
> I don't think there's much point in swerving over to the other side
> of the road to match Diaspora, because that just puts us in a head-on
> collision situation with the Java standard libraries (and a bunch of
> others). I think it's be better to lobby Diaspora, or submit a
> patch, to get it to comply with the spec. Unfortunately I'm not a
> Rubyista. Anyone?
>
The Diaspora "encrypted salmon" protocol is so far removed from the spec
that there's no point in making it compliant. It will never
inter-operate with any other salmon implementations. (They are also
appending linefeeds to each of the base64url'd signing components and
therefore signing the wrong data, but since it can't interoperate with
"textbook salmon" for a number of reasons I'm not too concerned about it).
I'll be working on a simple library for Friendika which can do the
sign/verify on PHP using openssl components and eliminate the need for
PHPseclib. Friendika has revoked copyright and licensing, so this
library will be freely available to anybody that wants it.
The question is that if I'm going through this effort, should I do it
the wrong way or the right way? Friendika doesn't use salmon for its own
communications. It only uses salmon for interop with external projects,
so if the other projects don't wish to change, I have no motivation for
doing it right.
It will take years to get a native crypto implementation into PHP which
exposes the correct methods.
I think the Ruby openssl implementation is in worse shape because it's
still using pkcs#1 keys (requiring key translation utilities for most
projects which wish to federate with Diaspora, as pkcs#1 is the salmon
key format made available with webfinger discovery, *not*
modulus/exponent). I've already created some key translation tools in
PHP which will quickly convert between pkcs#1, pkcs#8 and
modulus/exponent format.
Still, with gem packaging, one can potentially upgrade the Ruby crypto
library easily if it's available - much easier than with PHP.
I'm not aware of any native tools for dealing with modulus/exponent keys
in Ruby - so a similar toolkit (key conversion library and salmon
signing library) as what I'm building (basically an ASN.1 parser/encoder
and some key encoding logic) may still be needed on that platform to do
"textbook" salmon.
There's pain for many implementers no matter which way this turns. The
most pain free solution (though obviously not the best solution) would
be to declare "federated social web salmon" to be a bastard variant of
salmon which uses a different signing algorithm. This usage still might
need to be flagged somehow.
If a decision is made to start fixing it now, just as with the wrong
signed data bug I pointed out last year - there will be an awkward
transition period when both formats need to be supported and every
salmon communication may need to be duplicated until the transition is
complete.
I personally don't care how this is resolved. I'll build whatever works
with others - regardless of whether it's right or not.
This would be wonderful. I've been buried deep in low-level crypto code
for the last two weeks and don't enjoy it at all.
It appears that I was mistaken, and I'm now seeing the emsa padding
implementation from status.net compatible implementations. The low-level
signing details get pretty obscure to track through, so my sincere
apologies for raising unnecessary alarms.
For us out here in the trenches, usually all we have to work with is a
signature that doesn't verify - and have to walk through the entire
sign/verify sequence in both directions to figure out why not. This can
get quite complicated when the source and destination are on different
platforms.
But it also appears that there may be differing assumptions regarding
step 6 - "RSA sign the emsa byte sequence'. In some implementations the
requisite emsa padding is performed within the system's "RSA sign"
function, in some it is not, and this is not easily discoverable. The
hash algorithm used in "RSA sign" has not been specified (sha256 should
probably be assumed (?), but this is not spelled out and is not
available in all RSA implementations). There are also some questions
about whether or not the output signature (an encrypted blob) has been
subject to pkcs#1 padding.
It might be worth clarifying this last step just a wee bit more for the
benefit of future explorers and troubleshooters. It probably doesn't
require the same level of detail as the emsa padding process, but at
least a pointer to a spec or working example in some language.
On Tue, Aug 2, 2011 at 9:39 PM, Mike Macgirvin <mi...@macgirvin.com> wrote:
>> But really the meta-point here is that we desperately need a simple
>> live interop tester that takes signed blobs and says "does this
>> signature check out?" in order to check interop.
>
>
> This would be wonderful. I've been buried deep in low-level crypto code
> for the last two weeks and don't enjoy it at all.
I would second this. I know when John, Charlie and I were working on
the StatusNet / Cliqset integration we did a lot of "do you get this
signature?" back 'n' forth. A simple validator service would be
wonderful.
> It appears that I was mistaken, and I'm now seeing the emsa padding
> implementation from status.net compatible implementations. The low-level
> signing details get pretty obscure to track through, so my sincere
> apologies for raising unnecessary alarms.
I know last I touched it (which is getting to be a while ago now), the
StatusNet (phpseclib) signing code was fully interoperable with the
java library and the python code that John had at the time.
Glad to hear this might still be the case!
> For us out here in the trenches, usually all we have to work with is a
> signature that doesn't verify - and have to walk through the entire
> sign/verify sequence in both directions to figure out why not. This can
> get quite complicated when the source and destination are on different
> platforms.
>
> But it also appears that there may be differing assumptions regarding
> step 6 - "RSA sign the emsa byte sequence'. In some implementations the
> requisite emsa padding is performed within the system's "RSA sign"
> function, in some it is not, and this is not easily discoverable. The
> hash algorithm used in "RSA sign" has not been specified (sha256 should
> probably be assumed (?), but this is not spelled out and is not
> available in all RSA implementations). There are also some questions
> about whether or not the output signature (an encrypted blob) has been
> subject to pkcs#1 padding.
>
> It might be worth clarifying this last step just a wee bit more for the
> benefit of future explorers and troubleshooters. It probably doesn't
> require the same level of detail as the emsa padding process, but at
> least a pointer to a spec or working example in some language.
Agreed - I will say in doing this stuff over the years - a simple
validator / reference implementation can go a *long* way to clarify
what can sometimes be tricky in spec language.
Cheers,
--
James Walker :: http://walkah.net/
> 1. Let hash = the SHA256 hash digest of M
> 2. Let prefix = the constant byte sequence [0x30, 0x31, 0x30, 0xd, 0x6, 0x9, 0x60, 0x86, 0x48, 0x1, 0x65, 0x3, 0x4, 0x2, 0x1, 0x5, 0x0, 0x4, 0x20]
> 3. Let k = the number of bytes in the public key modulus
> 4. Let padding = '\xFF' repeated (k - length(prefix+hash) - 3) times
> 5. Let emsa = '\x00' + '\x01' + padding + '\x00' + prefix + hash
> 6. RSA sign the emsa byte sequence
[John - Was recently wondering about the choice of the word 'sign' on
step 6. I think technically at step 6 we're just encrypting the emsa
blob with the author's private key. But I may be missing something.]
After some more digging I've actually come to question if this is the
case - and this is precisely what led to the initial confusion.
In fact I tried to duplicate a known signature by encrypting the emsa
sequence at this stage and was prohibited from doing so. The emsa bytes
and the encryption modulus were now exactly the same size and there are
a few bytes of overhead required.
Working backward from a signature and decrypting it with the public key
results in a 'hash structure' in all cases (the ASN.1 OID for SHA256 and
a hash).
This is why I raised this issue initially, because working backwards I
did *not* see the emsa padding bytes and felt that I should be seeing them.
It would still be nice to know a bit better what is happening at step 6,
but some test tools would be a more beneficial use of time.
> It appears that I was mistaken, and I'm now seeing the emsa padding
> implementation from status.net compatible implementations. The low-level
> signing details get pretty obscure to track through, so my sincere
> apologies for raising unnecessary alarms.I know last I touched it (which is getting to be a while ago now), the
StatusNet (phpseclib) signing code was fully interoperable with the
java library and the python code that John had at the time.
I was just about to fire off an email cc: evan to inquire about this,
but decided I've caused enough trouble for one week. IIRC James is no
longer directly involved with SN dev, but I'm not certain.
I've been ready to strip padding for months - just waiting for StatusNet
since that's where the bulk of our "OStatus salmon" traffic is exchanged
- and as opposed to "Diaspora salmon" which requires its very own
variant code.
Anyways, if Evan is reading this, please send an announcement ahead of
time so all of us can plan our migration strategies and project
communications accordingly.
To be fair, we (okay, I) didn't really step up and do what's truly needed: An online validator that anybody can ping to see whether they're doing it right.
Deal. I'm looking at the open source Java library that Charlie wrote
and at least I should be able to put something together that generates
good test data (and update the spec examples too).
But it's not interoperable to the spec.
Normally, I'd say change the spec to match the implementations. The
omitted EMSA padding however has its reason:
http://en.wikipedia.org/wiki/RSA#Attacks_against_plain_RSA
I want you implementers to commit to: let's drop compatibility to those
broken versions and fix the code according to the spec.
If interoperability is really crucial at this point of deployment, an
implementation could try sending Salmons with any possible variation,
falling back to the next upon verification error. The receiving part in
StatusNet already yields an HTTP error in that case.
Mind that such a strategy could expose the keys to chosen plaintext
attacks, just as it is the case for implementations w/o the padding
right now.
Astro
If it's any help to you, I'm using the java-salmon stack in Clojure for
my application. I'm just getting started with it, so my use is far from
optimal, I'm sure.
If it helps you at all, a good place to look is
https://github.com/duck1123/jiksnu/blob/master/src/main/clojure/jiksnu/model/signature.clj