[e-lang] RumpelTree++

Discussion:

Rob Meijer

2014-07-21 11:51:47 UTC

I thought some of you might be interested in the following.

I've migrated my Rumpelstiltskin tree-graph algorithm code from using
openssl to using crypto++, and from being some deep part of MinorFS2 to
being its own hopefully more widely usable C++ library. Its still a work
in progress (need to write a whole lot of extra tests, need to look at
memory wiping that seems not to be working, and at writing a solid cmake
config file without hard-coded llvm tools, but anyhow, I think its in a
state that its suitable to play around with a bit for those interested in
using it.

https://github.com/pibara/Rumpeltreepp

I'm very interested in any feedback, and if anyone thinks it usefull that
I've seperated my code from MinorFs2 into a seperate general purpose
library.

The interface of the library is defined in rumpelstiltskin.hpp, and an API
usage example can be found in test.cpp.

Rob

Rob Meijer

2014-07-21 12:11:35 UTC

Permalink

Oops, that one should have gone to cap-talk, not e-lang :-(

Post by Rob Meijer
I thought some of you might be interested in the following.
I've migrated my Rumpelstiltskin tree-graph algorithm code from using
openssl to using crypto++, and from being some deep part of MinorFS2 to
being its own hopefully more widely usable C++ library. Its still a work
in progress (need to write a whole lot of extra tests, need to look at
memory wiping that seems not to be working, and at writing a solid cmake
config file without hard-coded llvm tools, but anyhow, I think its in a
state that its suitable to play around with a bit for those interested in
using it.
https://github.com/pibara/Rumpeltreepp
I'm very interested in any feedback, and if anyone thinks it usefull that
I've seperated my code from MinorFs2 into a seperate general purpose
library.
The interface of the library is defined in rumpelstiltskin.hpp, and an API
usage example can be found in test.cpp.
Rob
_______________________________________________
e-lang mailing list
http://www.eros-os.org/mailman/listinfo/e-lang

Rob Meijer

2014-07-25 18:42:20 UTC

Permalink

Just did a last bugfix. All tests run correctly and without memory leaks.
Would anyone be interested in contributing a security-oriented code-review
on my library? Its C++11 code and I took extra effort to make sure memory
containing security sensitive authority tokens gets wiped after usage
while maintaining the friendly almost fully string like interface.

T.I.A.

Rob

Post by Rob Meijer
Oops, that one should have gone to cap-talk, not e-lang :-(

_______________________________________________
cap-talk mailing list
http://www.eros-os.org/mailman/listinfo/cap-talk

Raoul Duke

2014-07-25 18:51:18 UTC

Permalink

Post by Rob Meijer
Would anyone be interested in contributing a security-oriented code-review
on my library? Its C++11 code and I took extra effort to make sure memory
containing security sensitive authority tokens gets wiped after usage
while maintaining the friendly almost fully string like interface.

this is a sincere but neophyte question, i do not mean it in a snarky
way, but is anything written in C++ able to be considered safe or
secure? or are the definitions of safe and secure meant to be taken
relative to the fact that it is all written in C++?

thank you.

Rob Meijer

2014-07-25 21:14:18 UTC

Permalink

Post by Raoul Duke

Fair question. The security measures I took were with respect to malloc
attacks. I think that from the perspective of malloc attacks, low level
memory insecure languages might actually be the only ones available to
allow any defence. The library is providing a sparse cap frame for DAG
shaped hierarchies. The thread model is: other processes gaining access to
these authoritative tokens. If at any time a process holding such
sparse-caps ends and a hostile process manages to malloc a page that still
holds the old process its sparsecaps, than the relevant security property
would have been broken. If in C++ I can manage to clear the relevant
memory location prior to deallocation and thus most importantly, prior to
pages being reassigned to hostile processes, while in a memory safe or
even ocap language I could not guarantee this, than memory insecurity in
my specific case paradoxaly seems to actually be a virtue.

(sidenote: if swap is enabled all efforts could be futile)

I hope the above makes some sense.

Rob

Post by Raoul Duke
_______________________________________________
e-lang mailing list
http://www.eros-os.org/mailman/listinfo/e-lang

Rob Meijer

2014-08-02 11:03:12 UTC

Permalink

For most of you on cap-talk this will probably all be old/known stuff, but
to make sure I communicate the urgency of my plea for a peer review of the
code of this library, let me draw a dense context.

Some years ago I wrote a set proof of concept implementation of a set of
cooperating least authority providing user space file-systems for AppArmor
based Linux systems. This proof of concept was/is called MinorFS. For some
context, here is a Linux Journal article I wrote on this system 5 years
ago.

http://www.linuxjournal.com/magazine/minorfs

At the core of these file systems was a sparsecap (or password capability
if you prefer that term) file-system called capfs. This file-system was
based on an sqlite database with sparsecap to path mappings.

Some time later, I came up with an alternative hash based algorithm that
could possibly do away with the need of a database for capfs. After asking
feedback on this algorithm on the cap-talk mailing list, David Barbour
suggested I' d use HMAC instead of just SHA.

http://www.eros-os.org/pipermail/cap-talk/2012-February/015332.html

Resulting from this feedback, and driven by the idea that a library for
sparsecaps that give access to a DAG shaped authority structure might be
usefull for other things than just a rewrite of Minorfs::capfs, I recently
created a C++ (c++11) library that implements the algorithm, using
crypto++ for its hmac/sha2 crypto primitives.

https://github.com/pibara/Rumpeltreepp

This library basically implements the algorithm described here:

http://minorfs.wordpress.com/2014/02/20/rumpelstiltskin-and-his-children/

http://minorfs.wordpress.com/2014/03/21/rumpelstiltskin-and-his-children-part-2/

Given the fact that my crypto knowledge and my knowledge regarding
implementation and usage pitfalls is relatively limited, I desperately
need a peer review on my Rumpleltree++ source code. When the file-system
in finished, the logic in this library will become a pivotal part of the
TCB of any system built using the full set of file systems that will be
layered on them together with AppArmor. A rewrite of the original MinorFS
that wil aim at retrofitting the taming of shared mutable file system
provided by MinorFS to non MinorFS aware applications in a way that should
help mitigate the effects that Trojans might have in a major way:

http://www.slideshare.net/RobMeijer3/ohm2013-trojans-slides

Thus, if anyone would be able and willing to contribute a peer review to
this library, you will be playing a crucial role in the ultimate goal of
creating a trojan free environment.

Tnx,

Rob

Post by Rob Meijer
Just did a last bugfix. All tests run correctly and without memory leaks.
Would anyone be interested in contributing a security-oriented code-review
on my library? Its C++11 code and I took extra effort to make sure memory
containing security sensitive authority tokens gets wiped after usage
while maintaining the friendly almost fully string like interface.
T.I.A.
Rob

Post by Rob Meijer
Oops, that one should have gone to cap-talk, not e-lang :-(

_______________________________________________
cap-talk mailing list
http://www.eros-os.org/mailman/listinfo/cap-talk

Rob Meijer

2014-08-03 21:53:56 UTC

Permalink

Added a web page with some usage documentation:

http://pibara.github.io/Rumpeltreepp/

Anyone know a good place to find people who might be willing to contribute
a security and crypto oriented code-review?

T.I.A

Rob

Post by Rob Meijer
For most of you on cap-talk this will probably all be old/known stuff, but
to make sure I communicate the urgency of my plea for a peer review of the
code of this library, let me draw a dense context.
Some years ago I wrote a set proof of concept implementation of a set of
cooperating least authority providing user space file-systems for AppArmor
based Linux systems. This proof of concept was/is called MinorFS. For some
context, here is a Linux Journal article I wrote on this system 5 years
ago.
http://www.linuxjournal.com/magazine/minorfs
At the core of these file systems was a sparsecap (or password capability
if you prefer that term) file-system called capfs. This file-system was
based on an sqlite database with sparsecap to path mappings.
Some time later, I came up with an alternative hash based algorithm that
could possibly do away with the need of a database for capfs. After asking
feedback on this algorithm on the cap-talk mailing list, David Barbour
suggested I' d use HMAC instead of just SHA.
http://www.eros-os.org/pipermail/cap-talk/2012-February/015332.html
Resulting from this feedback, and driven by the idea that a library for
sparsecaps that give access to a DAG shaped authority structure might be
usefull for other things than just a rewrite of Minorfs::capfs, I recently
created a C++ (c++11) library that implements the algorithm, using
crypto++ for its hmac/sha2 crypto primitives.
https://github.com/pibara/Rumpeltreepp
http://minorfs.wordpress.com/2014/02/20/rumpelstiltskin-and-his-children/
http://minorfs.wordpress.com/2014/03/21/rumpelstiltskin-and-his-children-part-2/
Given the fact that my crypto knowledge and my knowledge regarding
implementation and usage pitfalls is relatively limited, I desperately
need a peer review on my Rumpleltree++ source code. When the file-system
in finished, the logic in this library will become a pivotal part of the
TCB of any system built using the full set of file systems that will be
layered on them together with AppArmor. A rewrite of the original MinorFS
that wil aim at retrofitting the taming of shared mutable file system
provided by MinorFS to non MinorFS aware applications in a way that should
http://www.slideshare.net/RobMeijer3/ohm2013-trojans-slides
Thus, if anyone would be able and willing to contribute a peer review to
this library, you will be playing a crucial role in the ultimate goal of
creating a trojan free environment.
Tnx,
Rob

Post by Rob Meijer
Oops, that one should have gone to cap-talk, not e-lang :-(

_______________________________________________
cap-talk mailing list
http://www.eros-os.org/mailman/listinfo/cap-talk

Rob Meijer

2014-11-03 21:57:54 UTC

Permalink

I've recently been contemplating Rumpelstiltskin hash trees for my current
project, Wikilon, a wiki-based IDE and software platform oriented around
my
concatenative capability language, AO. Wikilon will provide a
filesystem-like abstraction, albeit oriented around the language.

Sounds interesting.

One question: to the best of your knowledge, is Rumpelstiltskin hash tree
patent encumbered in any way? Will it become so? I'd rather not deal with
that.

No, I'm highly allergic to patents myself, but next to that, aren't
computer algorithms excluded from patentability? In any case, in the worst
case we have the cap-talk mailing list archive to prove prior art ;-)

http://www.eros-os.org/pipermail/cap-talk/2012-February/thread.html

I have other approaches in mind if necessary, e.g. conventional
Type/ID/Auth/HMAC identifiers.
My second question is whether you've considered how to handle
*revocability*. For example, a user wishes to delegate an expert an
authority to poke around a bit, help with configuration of a service for
example, but wants to revoke the granted authority shortly after the help
is performed.

Not at that level. I'm still trying to come up with a 'storage-friendly'
caretaker like overlay, no luck yet though.

Seems to me that your Rumpelstiltskin tree hash doesn't really offer any
sort of attenuation on the temporal dimension.
With the more conventional model, I could add a token to the Auth field
representing a revocable authorization-path of sorts, and offer a few
methods to attenuate the session. Such IDs grow large quickly. An
appealing
aspect of your hash trees is the constant size identifier.

Post by Rob Meijer
http://pibara.github.io/Rumpeltreepp/
Anyone know a good place to find people who might be willing to contribute
a security and crypto oriented code-review?
T.I.A
Rob

Post by Rob Meijer
For most of you on cap-talk this will probably all be old/known stuff,

but

Post by Rob Meijer
to make sure I communicate the urgency of my plea for a peer review of

the

Post by Rob Meijer
code of this library, let me draw a dense context.
Some years ago I wrote a set proof of concept implementation of a set

Post by Rob Meijer
cooperating least authority providing user space file-systems for

AppArmor

Post by Rob Meijer
based Linux systems. This proof of concept was/is called MinorFS. For

some

Post by Rob Meijer
context, here is a Linux Journal article I wrote on this system 5

years

Post by Rob Meijer
ago.
http://www.linuxjournal.com/magazine/minorfs
At the core of these file systems was a sparsecap (or password

capability

Post by Rob Meijer
if you prefer that term) file-system called capfs. This file-system

was

Post by Rob Meijer
based on an sqlite database with sparsecap to path mappings.
Some time later, I came up with an alternative hash based algorithm

that

Post by Rob Meijer
could possibly do away with the need of a database for capfs. After

asking

Post by Rob Meijer
feedback on this algorithm on the cap-talk mailing list, David Barbour
suggested I' d use HMAC instead of just SHA.
http://www.eros-os.org/pipermail/cap-talk/2012-February/015332.html
Resulting from this feedback, and driven by the idea that a library

for

Post by Rob Meijer
sparsecaps that give access to a DAG shaped authority structure might

Post by Rob Meijer
usefull for other things than just a rewrite of Minorfs::capfs, I

recently

Post by Rob Meijer
created a C++ (c++11) library that implements the algorithm, using
crypto++ for its hmac/sha2 crypto primitives.
https://github.com/pibara/Rumpeltreepp

http://minorfs.wordpress.com/2014/02/20/rumpelstiltskin-and-his-children/
http://minorfs.wordpress.com/2014/03/21/rumpelstiltskin-and-his-children-part-2/

Post by Rob Meijer
Given the fact that my crypto knowledge and my knowledge regarding
implementation and usage pitfalls is relatively limited, I desperately
need a peer review on my Rumpleltree++ source code. When the

file-system

Post by Rob Meijer
in finished, the logic in this library will become a pivotal part of

the

Post by Rob Meijer
TCB of any system built using the full set of file systems that will

Post by Rob Meijer
layered on them together with AppArmor. A rewrite of the original

MinorFS

Post by Rob Meijer
that wil aim at retrofitting the taming of shared mutable file system
provided by MinorFS to non MinorFS aware applications in a way that

should

Post by Rob Meijer
http://www.slideshare.net/RobMeijer3/ohm2013-trojans-slides
Thus, if anyone would be able and willing to contribute a peer review

Post by Rob Meijer
this library, you will be playing a crucial role in the ultimate goal

Post by Rob Meijer
creating a trojan free environment.
Tnx,
Rob

Post by Rob Meijer
Oops, that one should have gone to cap-talk, not e-lang :-(

Post by Rob Meijer
I thought some of you might be interested in the following.
I've migrated my Rumpelstiltskin tree-graph algorithm code from

using

Post by Rob Meijer

Post by Rob Meijer
openssl to using crypto++, and from being some deep part of

MinorFS2

Post by Rob Meijer

Post by Rob Meijer
to
being its own hopefully more widely usable C++ library. Its still a work
in progress (need to write a whole lot of extra tests, need to look

Post by Rob Meijer

Post by Rob Meijer
memory wiping that seems not to be working, and at writing a solid cmake
config file without hard-coded llvm tools, but anyhow, I think its

Post by Rob Meijer

Post by Rob Meijer
a
state that its suitable to play around with a bit for those

interested

Post by Rob Meijer

Post by Rob Meijer
in
using it.
https://github.com/pibara/Rumpeltreepp
I'm very interested in any feedback, and if anyone thinks it

usefull

Post by Rob Meijer

Post by Rob Meijer
that
I've seperated my code from MinorFs2 into a seperate general

purpose

Post by Rob Meijer

Post by Rob Meijer
library.
The interface of the library is defined in rumpelstiltskin.hpp, and

Post by Rob Meijer

Post by Rob Meijer
API
usage example can be found in test.cpp.
Rob
_______________________________________________
e-lang mailing list
http://www.eros-os.org/mailman/listinfo/e-lang

_______________________________________________
cap-talk mailing list
http://www.eros-os.org/mailman/listinfo/cap-talk

Bill Frantz

2014-07-26 03:05:10 UTC

Permalink

Post by Rob Meijer
(sidenote: if swap is enabled all efforts could be futile)

Encrypted swap might be a solution. If the machine is capable of
hibernating, then the key for the encrypted swap has to be
written to disk and might be recovered from there.

Cheers - Bill

---------------------------------------------------------------------------
Bill Frantz |"We used to quip that "password" is the most common
408-356-8506 | password. Now it's 'password1.' Who said
users haven't
www.pwpconsult.com | learned anything about security?" -- Bruce Schneier

Rob Meijer

2014-07-26 14:34:24 UTC

Permalink

Actually neither hybernation nor the swap not being encrypted are the main
issue. Consider the following scenario:

1) Alice stores a secret in her process memory at virtual location A
mapping to real address B.
2) A gets swapped to disk, B gets added to the pool of available pages.
3) ...
4) A gets paged back to memory but now virtual location A maps to real
address C.
5) Alice wipes virtual location A and thus real location C.

Now at any time (during 3 or theoretically possibly even later) Mallet may
malloc a new page that just happens to be B with the non-wiped version of
the secret.

Rob

Post by Bill Frantz

Post by Rob Meijer
(sidenote: if swap is enabled all efforts could be futile)

Encrypted swap might be a solution. If the machine is capable of
hibernating, then the key for the encrypted swap has to be
written to disk and might be recovered from there.
Cheers - Bill
---------------------------------------------------------------------------
Bill Frantz |"We used to quip that "password" is the most common
408-356-8506 | password. Now it's 'password1.' Who said
users haven't
www.pwpconsult.com | learned anything about security?" -- Bruce Schneier
_______________________________________________
e-lang mailing list
http://www.eros-os.org/mailman/listinfo/e-lang

Bill Frantz

2014-07-26 22:11:26 UTC

Permalink

Post by Rob Meijer
1) Alice stores a secret in her process memory at virtual location A
mapping to real address B.
2) A gets swapped to disk, B gets added to the pool of available pages.
3) ...
4) A gets paged back to memory but now virtual location A maps to real
address C.
5) Alice wipes virtual location A and thus real location C.
Now at any time (during 3 or theoretically possibly even later) Mallet may
malloc a new page that just happens to be B with the non-wiped version of
the secret.

I guess I'm completely obsolete. I thought all real systems with
any security story at all would zero pages being allocated
across security boundaries. KeyKOS/CapROS etc. do. What systems don't?

Cheers - Bill

-----------------------------------------------------------------------
Bill Frantz | gets() remains as a monument | Periwinkle
(408)356-8506 | to C's continuing support of | 16345
Englewood Ave
www.pwpconsult.com | buffer overruns. | Los Gatos,
CA 95032

Jonathan S. Shapiro

2014-07-27 19:10:38 UTC

Permalink

Post by Bill Frantz
I guess I'm completely obsolete. I thought all real systems with
any security story at all would zero pages being allocated
across security boundaries. KeyKOS/CapROS etc. do. What systems don't?

I'm not aware of *any* mainstream operating systems that allocate non-zero
pages to malloc.

There used to be some cases in UNIX/Linux where the transfer of data in
(e.g.) a write call that copies data from user space to file buffer pages
might skip zeroing of the buffer page if and only if the entire kernel
buffer page is being overwritten. What happened if a page fault occurred in
mid-transfer and the application had registered a signal handler for
SIGSEGV in this case was never clear to me. A subsequent read() from that
buffer page would honor the transfer length limit, but if the buffer page
is mmap'd... Oh. No. If it's mmap'd then the page zero will have already
occurred before the mmap proceeded.

These days, I believe most UNIX systems strictly maintain the rule of "page
zero before allocate", though they *do* use permission and status bits to
implement just-in-time zero in the event that background zeroing logic
hasn't gotten to the frame in time. WIndows and OSX do this as well. I'm
not sure about mobile OSs.

shap

Rob Meijer

2014-07-27 20:27:22 UTC

Permalink

So would you say in-process zeroing of secrets after usage to protect
against malloc attacks has become totally unneeded?

Post by Jonathan S. Shapiro

I'm not aware of *any* mainstream operating systems that allocate non-zero
pages to malloc.
There used to be some cases in UNIX/Linux where the transfer of data in
(e.g.) a write call that copies data from user space to file buffer pages
might skip zeroing of the buffer page if and only if the entire kernel
buffer page is being overwritten. What happened if a page fault occurred in
mid-transfer and the application had registered a signal handler for
SIGSEGV in this case was never clear to me. A subsequent read() from that
buffer page would honor the transfer length limit, but if the buffer page
is mmap'd... Oh. No. If it's mmap'd then the page zero will have already
occurred before the mmap proceeded.
These days, I believe most UNIX systems strictly maintain the rule of "page
zero before allocate", though they *do* use permission and status bits to
implement just-in-time zero in the event that background zeroing logic
hasn't gotten to the frame in time. WIndows and OSX do this as well. I'm
not sure about mobile OSs.
shap
_______________________________________________
e-lang mailing list
http://www.eros-os.org/mailman/listinfo/e-lang

Jonathan S. Shapiro

2014-07-27 20:34:52 UTC

Permalink

Post by Rob Meijer
So would you say in-process zeroing of secrets after usage to protect
against malloc attacks has become totally unneeded?

No no. I never said that. In-process zeroing is *essential*. Mainly because
their are various ways to read in-process memory. I'm just saying that the
paging subsystem isn't the failure model you are guarding against.