Salmon magic signature implementations broken

[Astro]

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

[eschnou]

Hi Astro,

I totaly +1 on this, having spent too much time trying to get salmon interop working between node-ostatus and statusnet. I've not seen any successfull salmon interop with statusnet out there besides Thomas Koski mininme, which is however based on the same PHP library that status.net. It seems that most project failed to achieve salmon interop (diaspora, friendika, rstatus, etc.) which is a pity. Only cross-domain messaging is true federation. Pulling feeds over PuSH is not enough in my opinion.

Now, I'm unsure on Salmon's future. It is weird that your post did not even make it on the salmon list. I wonder if John Panzer can comment on this and shed some lights on the future of the spec in his opinion. It may be that Google has federation plans for +, but with another spec ? Shall we just wait or do we try to fix things ourselves and move on ?

In the short term, just finding a way to make salmon federation between status.net, node-ostatus, diaspora, friendika, etc... would be a good start. Filling the gaps in the spec, and agreeing on a test suite is a good start. Given the deployments of status.net out there, I imagine that aligning on their implementation may be the best.

In the long term, I would favor a broader approach to federation, looking more like the domain federation protocol of Martin Atkins [1]. Once you have domain level trust, it gets easier to have cross-domain messaging and to build various use cases on top of that. Instead of having different auth mechanism like we have now in salmon and pubsubhubub. Another good reference is Blaine's proposal on 'private web hooks'.

Cheers,

Laurent

[1] http://specs.mart.me.uk/dfp

[2] http://blog.romeda.org/2011/03/private-webhooks-private-feeds.html

[Mike Macgirvin]

> It seems that most project failed to achieve salmon interop
> (diaspora, friendika, rstatus, etc.) which is a pity.

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 Panzer]

Hi guys,

Sorry about the missed posts -- Google Groups spam control blocks
first time posters, and I may have missed the notification.

Mike, your post clearly describes the issue. There are some "magic
bytes" that need to be in place to make things be compliant with the
(alphabet soup) of specs involved with security. Just to be clear,
the _only reason_ to comply with those specs is to make Salmon
signatures compatible and interoperable with existing libraries (like
the Java cryptography libraries, for example). I went through this
exact sequence of steps last year, and that's why the spec spells out
in excruciating detail how to do the (EMSA) padding in section 7.1:

http://salmon-protocol.googlecode.com/svn/trunk/draft-panzer-magicsig-01.html#signing
Let hash = the SHA256 hash digest of M
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]
Let k = the number of bytes in the public key modulus
Let padding = '\xFF' repeated (k - length(prefix+hash) - 3) times
Let emsa = '\x00' + '\x01' + padding + '\x00' + prefix + hash
RSA sign the emsa byte sequence
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.

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?


--
John Panzer / Google
jpa...@google.com / abstractioneer.org / @jpanzer

[Mike Macgirvin]

>
> http://salmon-protocol.googlecode.com/svn/trunk/draft-panzer-magicsig-01.html#signing
>
> 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.]

> 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.

[John Panzer]

(Re-joining the forked cross-threaded conversations...)

There actually is a security issue here.

After doing a bit more research (searching my GMail) and checking with Ben Laurie, I realized why Salmon does the more complicated and seemingly arbitrary additional bytes:  There are important security properties proved for this particular method (with arbitrary messages M), and there aren't any for the "bare" signing that Diaspora is doing.  Thus the generally understood properties of "public key signatures" aren't what you get if you just do "bare" signing, so your local security folks will tell you not to use this for anything important.

And, since I implemented this in Python using stone knives and bearskins, I know it's not that hard to write...  just annoying.

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.  That's the only thing that got feeds halfway interoperating (http://feedvalidator.org).  Mea culpa, I intended to start on that last year but got busy (https://plus.google.com).  I would like to work on it some more soon, now that other things are a bit less pressing (but not much).

--
John Panzer / Google
jpa...@google.com / abstractioneer.org / @jpanzer

[Mike Macgirvin]

> 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.

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.

[James Walker]

Hey all, just digging the "on vacation" backlog...

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/

[John Panzer]

On Mon, Aug 1, 2011 at 7:18 PM, Mike Macgirvin <mi...@macgirvin.com> wrote:

>
> http://salmon-protocol.googlecode.com/svn/trunk/draft-panzer-magicsig-01.html#signing
>

>    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.]

Thanks yes: http://code.google.com/p/salmon-protocol/issues/detail?id=33

Yes, this is absolutely correct -- this is actually doing the RSA encryption of the emsa byte sequence using the private key.  

[Mike Macgirvin]

On 4/08/2011 10:47 AM, John Panzer wrote:
> Thanks yes: http://code.google.com/p/salmon-protocol/issues/detail?id=33
>
> Yes, this is absolutely correct -- this is actually doing the RSA
> encryption of the emsa byte sequence using the private key.

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.

[eschnou]

> 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.

James, last time I checked, there were other issues with the status.net implementation. In particular status.net does not strip the base64 padding as required in the latest release of the salmon spec. I had documented the issues here:

http://www.mail-archive.com/status...@lists.status.net/msg01464.html

What is confusing is that the example in the spec is flawed and has to be corrected, issue here:

http://code.google.com/p/salmon-protocol/issues/detail?id=31

[Mike Macgirvin]

> James, last time I checked, there were other issues with the
> status.net implementation. In particular status.net does not strip
> the base64 padding as required in the latest release of the salmon
> spec. I had documented the issues here:
> http://www.mail-archive.com/status...@lists.status.net/msg01464.html

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.

[Astro]

James Walker wrote:
> > 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!

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

[John Panzer]

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).

--
John Panzer / Google
jpa...@google.com / abstractioneer.org / @jpanzer

On Thu, Aug 4, 2011 at 9:19 AM, Hunter Freyer <hjfr...@google.com> wrote:
> Rejoining again from forked conversation:
>>
>> 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.
>
> So, a million years ago I forked and (hopefully) improved the magicsig
> python implementation, and then did nothing with it. I'm not sure how much
> the spec has changed, but it shouldn't be too hard to turn it into a web
> service if it still works.
> John, how about I make you a deal: give me a few examples of each of the
> following: public keys, private keys, raw messages, and messages signed by
> the aforementioned keys, in each of the formats that keys and messages and
> envelopes can come in, and I'll make sure my old code still works and hook
> it up to an appengine app. Deal?
> kthxbai,
> Hunter
>
>

[Hunter Freyer]

On Thu, Aug 4, 2011 at 12:41, John Panzer <jpa...@google.com> wrote:

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).

Is the Java library AppEngineable? Would it be a better candidate for reference implementation?

kthxbai,
Hunter