Eleganz: The Elegant Homebrew Manager

Hi everyone,

Last year, in January, I decided to have some fun and write a homebrew application using the EFL libraries. I decided to work on a homebrew manager.. basically a replacement to the XMB. It went really well, and the development was really fast, and it was all thanks to the awesome API and capabilities of the EFL libraries. However, I became busy and was unable to continue… also, it was a bit slow and without proper hardware acceleration, it wouldn’t be as good as I hoped for, so I put the project on the side.
After many months, in September, thanks to gzorin’s work, we finally had a working and usable GL implementation and the EFL apps automatically gained from it by becoming hardware accelerated. My homebrew manager was much better! but I still needed to finish a few things and I didn’t have time so I put to rest again.

Today, I have decided to release this homebrew application, *as is* for everyone’s enjoyment! This means that it is not fully working, it might still have some bugs here and there, but it is still a homebrew app that people can use and have some fun with. Most importantly it will serve 4 purposes :

  • Maybe re-awaken  this dying PS3 homebrew scene
  • Be a good “exercise to the community” for finishing it up
  • Be a good example of what can be done with the EFL
  • Bring non-developers into writing EFL themes for the app

 

I introduce to you, Eleganz! The Elegant Homebrew Manager! A little homebrew app that lets you install pkg files and run your games directly from it. Here is the mandatory screencast video :


YouTube Link toEleganz screencast

 

I have published my app in both github and on ps3dev’s gitorious. and you can also download a pre-compiled .pkg for your PS3 to have fun with it.

Here are some highglights of the application (features, limitations and bugs) :

  • The whole User Interface is completely customizable with themes
  • Installs .pkg files locally to its own data directory (won’t be visible in the real XMB, unless someone reverses the database format)
  • Does not yet run games (it’s for you to do it, use ps3load as reference maybe…)
  • Current theme is missing proper theme/images for the progressbar windows (default exquisite/E17 theme used)
  • System freezes for a few milliseconds when it tries to load a game’s background image (might be fixed if we implement a pthread library and threading support in the EFL)
  • Apparently crashes when it exits (bug)

The homebrew app comes with two themes, a dark and light theme. I like the dark one so I chose that as the default (oh, ignore that grey background ‘default’ one from that screencast video, that was just for testing). I wrote the user interface for the theme (the Edje files) while opium designed all the graphics. The theme engine in the EFL is extremely powerful, so I hope I will see tons of themes popping up. And I do not mean “change the images” themes, I want real themes, where the whole UI is different, a vertical XMB, a circular one, a 3D theme with perspective/depth for the icons, a dynamic/moving background, etc… You can learn about the .edj/.edc file format here and don’t forget to check the EDC reference wiki.

I hope to see the community pick this up and have fun with it!

That’s about it, enjoy it, and send me your patches! I’ll be waiting 🙂

KaKaRoTo

 

p.s: Forgot to say that the rules/naming conventions/etc.. of the EDC files are explained here. If a .edj file doesn’t have the appropriate parts/groups, then it will be ignored and will not show on the UI.

p.p.s: You can install the EFL on windows and have access to edje_cc to compile your .edc into .edj.

p.p.p.s: Damn, I  keep forgetting stuff.. by the way, the whole Eleganz application works just fine on the PC too, I did all my development on the PC (that screencast was actually on Linux), *then* I tried it on the PS3 and it just worked.. so for theme development, it should be pretty easy to test without the need of a PS3.

UVC H264 Encoding cameras support in GStreamer

More and more people are doing video conferencing everyday, and for that to be possible, the video has to be encoded before being sent over the network. The most efficient and most popular codec at this time is H264, and since the UVC (USB Video Class) specification 1.1, there is support for H264 encoding cameras.

One such camera is the Logitech C920. A really great camera which can produce a 1080p H264-encoded stream at 30 fps.  As part of my job for Collabora, I was tasked to add support for such a camera in GStreamer. After months of work, it’s finally done and has now been integrated upstream into gst-plugins-bad 0.10 (port to GST 1.0 pending).

One important aspect here is that when you are capturing a high quality, high resolution H264 stream, you don’t want to be wasting your CPU to decode your own video in order to show a preview window during a video chat, so it was important for me to be able to capture both H264 and raw data from the camera. For this reason, I have decided to create a camerabin2-style source: uvch264_src.

Uvch264_src is a source which implements the GstBaseCameraSrc API. This means that instead of the traditional ‘src’ pad, it provides instead three distinct source pads: vidsrc, imgsrc and vfsrc. The GstBaseCameraSrc API is based heavily on the concept of a “Camera” application for phones. As such, the vidsrc is meant as a source for recording video, imgsrc as a source for taking a single-picture and vfsrc as a source for the viewfinder (preview) window. A ‘mode’ property is used to switch between video-mode and image-mode for capture. The uvch264_src source only supports video mode however, and the imgsrc will never be used.

When the element goes to PLAYING, only the vfsrc will output data, and you have to send the “start-capture” action signal to activate the vidsrc/imgsrc pads, and send the “stop-capture” action signal to stop capturing from the vidsrc/imgsrc pads. Note that vfsrc will be outputting data when in PLAYING, so it must always be linked (link it to fakesink if you don’t need the preview, otherwise you’ll get a not-linked error). If you want to test this on the command line (gst-launch) you can set the ‘auto-start’ property to TRUE and the uvch264_src will automatically start the capture after going to PLAYING.

You can request H264, MJPG, and raw data from the vidsrc, but only MJPG and raw data from the vfsrc. When requesting H264 from the vidsrc, then the max resolution for the vfsrc will be 640×480, which can be served as jpg or as raw (decoded from jpg). So if you don’t want to use any CPU for decoding, you should ask for a raw resolution lower than 432×240 (with the C920) which will directly capture YUV from the camera. Any higher resolution won’t be able to go through the usb’s bandwidth and the preview will have to be captured in mjpg (uvch264_src will take care of that for you).

The source has two types of controls, the static controls which must be set in READY state, and DYNAMIC controls which can be dynamically changed in PLAYING state. The description of each property will specify whether that property is a static or dynamic control, as well as its flags. Here are the supported static controls : initial-bitrate, slice-units, slice-mode, iframe-period, usage-type, entropy, enable-sei, num-reorder-frames, preview-flipped and leaky-bucket-size. The dynamic controls are : rate-control,  fixed-framerate, level-idc, peak-bitrate, average-bitrate, min-iframe-qp,  max-iframe-qp, min-pframe-qp,  max-pframe-qp, min-bframe-qp,  max-bframe-qp, ltr-buffer-size and ltr-encoder-control.

Each control will have a minimum, maximum and default value, and those are specific to each camera and need to be probed when the element is in READY state. For that reason, I have added three element actions to the source in order to probe those settings : get-enum-setting, get-boolean-setting and get-int-setting.
These functions will return TRUE if the property is valid and the information was successfully retrieved, or FALSE if the property is invalid (giving an
invalid name or a boolean property to get_int_setting for example) or if the camera returned an error trying to probe its capabilities.
The prototype of the signals are :

  • gboolean get_enum_setting (GstElement *object, char *property, gint *mask, gint *default);
    Where the mask is a bit field specifying which enums can be set, where the bit being set is (1 << enum_value).
    For example, the ‘slice-mode’ enum can only be ignored (0) or slices/frame (3), so the mask returned would be : 0x09
    That is equivalent to (1 << 0 | 1 << 3) which is :
    (1 << UVC_H264_SLICEMODE_IGNORED) | (1 << UVC_H264_SLICEMODE_SLICEPERFRAME)
  • gboolean get_int_setting (GstElement *object, char *property, gint *min, gint *def, gint *max);
    This one gives the minimum, maximum and default values for a property. If a property has min and max to the same value, then the property cannot be changed, for example the C920 has num-reorder-frames setting: min=0, def=0 and max=0, and it means the C920 doesn’t support reorder frames.
  • gboolean get_boolean_setting (GstElement *object, char *property, gboolean *changeable, gboolean *default_value);
    The boolean value will have changeable=TRUE only if changing the property will have an effect on the encoder, for example, the C920 does not support the preview-flipped property, so that one would have changeable=FALSE (and default value is FALSE in this case), but it does support the enable-sei property so that one would have changeable=TRUE (with a default value of FALSE).

This should give you all the information you need to know which settings are available on the hardware, and from there, be able to control the properties
that are available.

Since these are element actions, they are called this way :

gboolean return_value, changeable, default_bool;
gint mask, minimum, maximum, default_int, default_enum;

g_signal_emit_by_name (G_OBJECT(element), "get-enum-setting", "slice-mode", &mask, &default_enum, &return_value, NULL);
g_signal_emit_by_name (G_OBJECT(element), "get-boolean-setting", "enable-sei", &changeable, &default_bool, &return_value, NULL);
g_signal_emit_by_name (G_OBJECT(element), "get-int-setting", "iframe-period", &minimum, &default_int &maximum, &return_value, NULL);

Apart from that, the source also supports the GstForceKeyUnit video event for dynamically requesting keyframes, as well as custom-upstream events to control LTR (Long-Term Reference frames), bitrate, QP, rate-control and level-idc, through, respectively, the uvc-h264-ltr-picture-control, uvc-h264-bitrate-control, uvc-h264-qp-control, uvc-h264-rate-control and uvc-h264-level-idc custom upstream events (read the code for more information!). The source also supports receiving the ‘renegotiate’ custom upstream event which will make it renegotiate the according to the caps on its pads. This is useful if you want to enable/disable h264 streaming or switch resolution/framerate easily while the pipeline is running; Simply change your caps and send the renegotiate event.

I have written a GUI test application which you can use to test the camera and the source’s various features. It can also serve as a reference implementation on how the source can be used. The test application resides in gst-plugins-bad, under tests/examples/uvch264/ (make sure to run it from its source directory though).

uvch264_src test application (click to enlarge)

You can also use this example gst-launch pipeline for testing the capture of the camera. This will capture a small preview window as well as an h264 stream in 1080p that will be decoded locally :

gst-launch uvch264_src device=/dev/video1 name=src auto-start=true src.vfsrc ! queue ! “video/x-raw-yuv,width=320,height=240,framerate=30/1” ! xvimagesink src.vidsrc ! queue ! video/x-h264,width=1920,height=1080,framerate=30/1,profile=constrained-baseline ! h264parse ! ffdec_h264 ! xvimagesink

That’s about it. If you are interested in using uvch264_src to capture from one of the UVC H264 encoding cameras, make sure you upgrade to the latest git versions of gstreamer, gst-plugins-base, gst-plugins-good and gst-plugins-bad (or 0.10.37+ for gstreamer/gst-plugins-base, 0.10.32 for gst-plugins-good and 0.10.24 for gst-plugins-bad, whenever those versions get released).

I would like to thank Collabora and Cisco for sponsoring me to work on this great project, it couldn’t have been possible without them!

If you have any more questions about this subject, feel free to contact me.

Enjoy!

RSXGL working and usable

Hi everyone!

When the PS3 homebrew scene started, a lot of people were complaining that it wasn’t possible to write 3D games for the PS3 because of its lack of OpenGL library.
Almost a year ago, Alex Betts thought he would tackle this problem and he started working on RSXGL… an implementation of the OpenGL 3.1 specification written from scratch targeting the PS3’s RSX. Anyone in their right mind would say that it’s impossible, that it’s too much work, but Alex spent the last year working on it, alone, until it became usable. You can read some news about it here.
For some reason though, no one used it to build their own apps. Maybe the status of the project was scaring them, it was said to be incomplete, there was no GLSL support, etc…
I am writing today to tell you that RSXGL is perfectly usable! It supports online GLSL compilation, as well as any feature you might want. As proof, I have written a new hardware accelerated engine for the EFL using RSXGL and it worked great! Alex and I spent a lot of time testing and fixing all the issues that were in RSXGL that were made visible by the EFL’s GL engine and I am happy to say that it’s working now. Expedite is able to run most of its tests at 50 to 60 fps on 1080p resolution (instead of the average of 5 to 10 fps it had on 720p before).
You can see performance tests right here (Running some tests from expedite) :
Software rendering: http://dl.dropbox.com/u/22642664/expedite_psl1ght.log
RSXGL rendering: http://dl.dropbox.com/u/22642664/expedite_rsxgl.log

Please give RSXGL a try. Also, you can get the latest EFL version from my repository, which includes the gl engine for ps3. Now, any EFL application will be automatically hardware accelerated thanks to RSXGL. I hope we can see some new games (or old GL games being ported) soon!

RSXGL : https://github.com/gzorin/RSXGL
EFL : https://github.com/kakaroto/e17

Enjoy!

Exquisite tool becomes a library!

The exquisite tool that comes with Enlightenment is a nice, pure edje application that is used for showing boot process splash screens. I thought it was a nice splash screen and more generally, a nice progress bar and wanted to use it in my own apps.

I have modified the exquisite tool to become a library so it can be used by others in their applications, while keeping the exquisite and exquisite-writer tools intact (they will now depend on libexquisite.so though).

Since it’s a very simple feature (only a couple hundred lines of code), the API is simple as well. Here’s an example of use :

  Evas_Object *obj = exquisite_object_add (evas, theme);
  evas_object_show (obj);

  exquisite_object_title_set (obj, "Title of the screen");
  exquisite_object_message_set (obj, "My Message");

  int test_id = exquisite_object_text_add (obj, "First test");
  int second_test = exquisite_object_text_add (obj, "Second text!");
  exquisite_object_status_set (obj, test_id, "FAIL", EXQUISITE_STATUS_TYPE_FAILURE);
  exquisite_object_status_set (obj, second_test, "OK", EXQUISITE_STATUS_TYPE_SUCCESS);

  exquisite_object_pulsate (obj);
  exquisite_object_progress_set (obj, 0.95);

That’s it, and you get a nice screen with title, message, text area for status messages (if you want it), and a progress bar. This also means you can use the default theme from exquisite or write your own using the same theme specification which can later on be used by others.

Please review the API provided, and this is the right time to suggest any changes to the API or to improve on the library, so let us know what you think!

Upgrading from Fedora 15 i686 to Fedora 16 x86_64

A couple of months ago I bought a new laptop with 8GB of RAM, but I realized I was running on a 32 bits system which meant I couldn’t use all my RAM. I had to switch to 64 bits. It takes so much time for me to restore my system that I didn’t have the courage to go through it again (did it last year, switched from Debian to Fedora, took me a week), so I stayed with 32 bits. Yesterday I had to upgrade to Fedora 16 and decided to do the switch to 64 bits at the same time… I’d like to share my experience with you!

First of all, I had to download the 64 bits version of the fedora CD which is not the default download on the website, I had to click on the small “more download options” to get the choice and I realized that’s how I got the 32 bit  install in the first place (Fedora download page should definitely list both links). Then I made a backup of all the installed packages on my system so I can restore them on the new system :

 yum -C info $(rpm -qa) | grep “Name   :” | cut -c 15- > packages-list.log

This will list all of the packages installed, and ask yum for the exact name of the package (instead of “git-1.7.6.5-1.fc15.i686”, it becomes “git”).. if you have a better method of doing that, let me know, but this did the trick for me.

Update: A better method was given to me by Hansen and Richard Godbee in the comments : rpm -qa –qf “%{name}\n” > packages-list.log

I obviously had a separate partition for the  /home directory, which made things easier, so I backed up in it the important directories which were: /opt, /root, /etc, /usr/local and my scratchbox home dir. Then the moment of truth, reboot into the live cd, install it, make sure not to format the /home partition, and reboot into the new 64 bits system.

First of all, as soon as I tried to login, gnome 3 would completely crash and would not let me log in, so I had to create a new user, login into gnome 3, then “ls -la” the files in the new user’s home dir, then delete (move away) those same files/directories from my own home dir, so that gnome doens’t crash anymore… apparently, my settings suddenly became incompatible or something… It’s important to note that I had some further problems later and I had to copy back .gnome2/keyrings otherwise the gnome-keyring daemon would freeze.

To restore all the packages that I had before, I first had to re-install (manually) the rpmfusion repository (free and nonfree), then I just did a simple :

yum install $(cat packages-list.log)

And after 1.2GB of downloads and 1020 package installs, my system was technically “restored” to how it was before the format. I look at the “No package foobar” lines given by yum at that point which told me what I needed to install manually (opera, skype, dropbox), which I did, and a few libs that apparently don’t exist anymore in Fedora 16. Now I just had to restore the /opt for some apps I had in there (and recompile the EFL/E17),  copy the Enlightenment.desktop file to /usr/share/xsessions, restore my /etc/hosts (which had some custom entries), restore some custom scripts I wrote into /usr/local/bin and recompile the libraries I was working on and had installed in /usr/local (gstreamer, libnice, farstream). I also had to install a few 32 bit libraries so I could install skype (which only comes in 32 bit flavor).

It took me about a day of work/compilation, but now I feel back home, don’t notice any difference in my system other than the fact that I will now be writing 32-bits bugs instead of 64-bits bugs 🙂

 

 

How the ECDSA algorithm works

To popular demand, I have decided to try and explain how the ECDSA algorithm works. I’ve been struggling a bit to understand it properly and while I found a lot of documentation about it, I haven’t really found any “ECDSA for newbies” anywhere. So I thought it would be good to explain in simple terms how it works so others can learn from my research. I have found some websites that explain the basic principles but nowhere near enough to actually understand it, others that explains things without any basics, making it incomprehensible, and others that go way too deep into the the mathematics behind it.

ECDSA stands for “Elliptic Curve Digital Signature Algorithm”, it’s used to create a digital signature of data (a file for example) in order to allow you to verify its authenticity without compromising its security. Think of it like a real signature, you can recognize someone’s signature, but you can’t forge it without others knowing. The ECDSA algorithm is basically all about mathematics.. so I think it’s important to start by saying : “hey kids, don’t slack off at school, listen to your teachers, that stuff might be useful for you some day!” 🙂 But these maths are fairly complicated, so while I’ll try to vulgarize it and make it understandable for non technical people, you will still probably need some knowledge in mathematics to understand it properly. I will do this in two parts, one that is a sort of high level explanation about how it works, and another where I dig deeper into its inner workings to complete your understanding. Note however that I’ve just recently learned this stuff, so I’m definitely not an expert on the matter.

So the principle is simple, you have a mathematical equation which draws a curve on a graph, and you choose a random point on that curve and consider that your point of origin. Then you generate a random number, this is your private key, you do some magical mathematical equation using that random number and that “point of origin” and you get a second point on the curve, that’s your public key. When you want to sign a file, you will use this private key (the random number) with a hash of the file (a unique number to represent the file) into a magical equation and that will give you your signature. The signature itself is divided into two parts, called R and S. In order to verify that the signature is correct, you only need the public key (that point on the curve that was generated using the private key) and you put that into another magical equation with one part of the signature (S), and if it was signed correctly using the the private key, it will give you the other part of the signature (R). So to make it short, a signature consists of two numbers, R and S, and you use a private key to generate R and S, and if a mathematical equation using the public key and S gives you R, then the signature is valid. There is no way to know the private key or to create a signature using only the public key.

Alright, now for the more in depth understanding, I suggest you take an aspirin right now as this might hurt! 😛

Let’s start with the basics (which may be boring for people who know about it, but is mandatory for those who don’t) : ECDSA uses only integer mathematics, there are no floating points (this means possible values are 1, 2, 3, etc.. but not 1.5..),  also, the range of the numbers is bound by how many bits are used in the signature (more bits means higher numbers, means more security as it becomes harder to ‘guess’ the critical numbers used in the equation), as you should know, computers use ‘bits’ to represent data, a bit is a ‘digit’ in binary notation (0 and 1) and 8 bits represent one byte. Every time you add one bit, the maximum number that can be represented doubles, with 4 bits you can represent values 0 to 15 (for a total of 16 possible values), with 5 bits, you can represent 32 values, with 6 bits, you can represent 64 values, etc.. one byte (8 bits) can represent 256 values, and 32 bits can represent 4294967296 values (4 Giga).. Usually ECDSA will use 160 bits total, so that makes… well, a very huge number with 49 digits in it…

ECDSA is used with a SHA1 cryptographic hash of the message to sign (the file). A hash is simply another mathematical equation that you apply on every byte of data which will give you a number that is unique to your data. Like for example, the sum of the values of all bytes may be considered a very dumb hash function. So if anything changes in the message (the file) then the hash will be completely different. In the case of the SHA1 hash algorithm, it will always be 20 bytes (160 bits). It’s very useful to validate that a file has not been modified or corrupted, you get the 20 bytes hash for a file of any size, and you can easily recalculate that hash to make sure it matches. What ECDSA signs is actually that hash, so if the data changes, the hash changes, and the signature isn’t valid anymore.

Now, how does it work? Well Elliptic Curve cryptography is based on an equation of the form :

y^2 = (x^3 + a * x + b) mod p

First thing you notice is that there is a modulo and that the ‘y‘ is a square. This means that for any x coordinate, you will have two values of y and that the curve is symmetric on the X axis. The modulo is a prime number and makes sure that all the values are within our range of 160 bits and it allows the use of “modular square root” and “modular multiplicative inverse” mathematics which make calculating stuff easier (I think). Since we have a modulo (p) , it means that the possible values of y^2 are between  0 and p-1, which gives us p total possible values. However, since we are dealing with integers, only a smaller subset of those values will be a “perfect square” (the square value of two integers), which gives us N possible points on the curve where N < p (N being the number of perfect squares between 0 and p). Since each x will yield two points (positive and negative values of the square-root of y^2), this means that there are N/2 possible ‘x‘ coordinates that are valid and that give a point on the curve. So this elliptic curve has a finite number of points on it, and it’s all because of the integer calculations and the modulus. Another thing you need to know about Elliptic curves, is the notion of “point addition“. It is defined as adding one point P to another point Q will lead to a point S such that if you draw a line from P to Q, it will intersect the curve on a third point R which is the negative value of S (remember that the curve is symmetric on the X axis). In this case, we define R = -S to represent the symmetrical point of R on the X axis. This is easier to illustrate with an image : So you can see a curve of the form y^2 = x^3 + ax + b (where a = -4 and b = 0), which is symmetric on the X axis, and where P+Q is the symmetrical point through X of the point R which is the third intersection of a line going from P to Q. In the same manner, if you do P + P,  it will be the symmetrical point of R which is the intersection of the line that is a tangent to the point P.. And P + P + P is the addition between the resulting point of P+P with the point P since P + P + P can be written as (P+P) + P.. This defines the “point multiplication” where k*P is the addition of the point P to itself k times… here are two examples showing this :  

Here, you can see two elliptic curves, and a point P from which you draw the tangent, it intersects the curve with a third point, and its symmetric point it 2P, then from there, you draw a line from 2P and P and it will intersect the curve, and the symmetrical point is 3P. etc… you can keep doing that for the point multiplication. You can also already guess why you need to take the symmetric point of R when doing the addition, otherwise, multiple additions of the same point will always give the same line and the same three intersections.

One particularity of this point multiplication is that if you have a point R = k*P, where you know R and you know P, there is no way to find out what the value of ‘k‘ is. Since there is no point subtraction or point division, you cannot just resolve k = R/P. Also, since you could be doing millions of  point additions, you will just end up on another point on the curve, and you’d have no way of knowing “how” you got there. You can’t reverse this operation, and you can’t find the value ‘k‘ which was multiplied with your point P to give you the resulting point R.

This thing where you can’t find the multiplicand even when you know the original and destination points is the whole basis of the security behind the ECDSA algorithm, and the principle is called a “trap door function“.

Now that we’ve handled the “basics”, let’s talk about the actual ECDSA signature algorithm. For ECDSA, you first need to know your curve parameters, those are a, b, p, N and G. You already know that ‘a‘ and ‘b‘ are the parameters of the curve function (y^2 = x^3 + ax + b), that ‘p‘ is the prime modulus,  and that ‘N‘ is the number of points of the curve, but there is also ‘G‘ that is needed for ECDSA, and it represents a ‘reference point’ or a point of origin if you prefer. Those curve parameters are important and without knowing them, you obviously can’t sign or verify a signature. Yes, verifying a signature isn’t just about knowing the public key, you also need to know the curve parameters for which this public key is derived from.

So first of all, you will have a private and a public key.. the private key is a random number (of 20 bytes) that is generated, and the public key is a point on the curve generated from the point multiplication of G with the private key. We set ‘dA‘ as the private key (random number) and ‘Qa‘ as the public key (a point), so we have : Qa = dA * G (where G is the point of reference in the curve parameters).

So how do you sign a file/message ? First, you need to know that the signature is 40 bytes and is represented by two values of 20 bytes each, the first one is called R and the second one is called S.. so the pair (R, S) together is your ECDSA signature.. now here’s how you can create those two values in order to sign a file.. first you must generate a random value ‘k‘ (of 20 byes), and use point multiplication to calculate the point P=k*G. That point’s x value will represent ‘R‘. Since the point on the curve P is represented by its (x, y) coordinates (each being 20 bytes long), you only need the ‘x‘ value (20 bytes) for the signature, and that value will be called ‘R‘. Now all you need is the ‘S‘ value.

To calculate S, you must make a SHA1 hash of the message, this gives you a 20 bytes value that you will consider as a very huge integer number and we’ll call it ‘z‘. Now you can calculate S using the equation :

S = k^-1 (z + dA * R) mod p

Note here the k^-1 which is the ‘modular multiplicative inverse‘ of k… it’s basically the inverse of k, but since we are dealing with integer numbers, then that’s not possible, so it’s a number such that (k^-1 * k ) mod p is equal to 1. And again, I remind you that k is the random number used to generate R, z is the hash of the message to sign, dA is the private key and R is the x coordinate of k*G (where G is the point of origin of the curve parameters).

Now that you have your signature, you want to verify it, it’s also quite simple, and you only need the public key (and curve parameters of course) to do that. You use this equation to calculate a point P :

P=  S^-1*z*G + S^-1 * R * Qa

If the x coordinate of the point P is equal to R, that means that the signature is valid, otherwise it’s not.

Pretty simple, huh? now let’s see why and how… and this is going to require some mathematics to verify :

We have :

P = S^-1*z*G + S^-1 * R *Qa

but Qa = dA*G, so:

P = S^-1*z*G + S^-1 * R * dA*G = S^-1 (z + dA* R) * G

But the x coordinate of P must match R and R is the x coordinate of k * G, which means that :

k*G = S^-1 (z + dA * R) *G

we can simplify by removing G which gives us :

k = S^-1(z + dA * R)

by inverting k and S, we get :

S = k^-1 (z + dA *R)

and that is the equation used to generate the signature.. so it matches, and that is the reason why you can verify the signature with it.

You can note that you need both ‘k‘ (random number) and ‘dA‘ (the private key) in order to calculate S, but you only need R and Qa (public key) to validate the signature. And since R=k*G and Qa = dA*G and because of the trap door function in the ECDSA point multiplication (explained above), we cannot calculate dA or k from knowing Qa and R, this makes the ECDSA algorithm secure, there is no way of finding the private keys, and there is no way of faking a signature without knowing the private key.

The ECDSA algorithm is used everywhere and has not been cracked and it is a vital part of most of today’s security.

Now I’ll discuss on how and why the ECDSA signatures that Sony  used in the PS3 were faulty and how it allowed us to gain access to their private key.

So you remember the equations needed to generate a signature.. R = k*G and S= k^-1(z + dA*R) mod p.. well this equation’s strength is in the fact that you have one equation with two unknowns (k and dA) so there is no way to determine either one of those. However, the security of the algorithm is based on its implementation and it’s important to make sure that ‘k‘ is randomly generated and that there is no way that someone can guess, calculate, or use a timing attack or any other type of attack in order to find the random value ‘k‘. But Sony made a huge mistake in their implementation, they used the same value for ‘k‘ everywhere, which means that if you have two signatures, both with the same k, then they will both have the same R value, and it means that you can calculate k using two S signatures of two files with hashes z and z’ and signatures S and S’ respectively :

S – S’ = k^-1 (z + dA*R) – k^-1 (z’ + da*R) = k^-1 (z + da*R – z’ -dA*R) = k^-1 (z – z’)

So : k = (z – z’) / (S – S’)

Once you know k, then the equation  for S because one equation with one unknown and is then easily resolved for dA :

dA = (S*k – z) / R

Once you know the private key dA, you can now sign your files and the PS3 will recognize it as an authentic file signed by Sony. This is why it’s important to make sure that the random number used for generating the signature is actually “cryptographically random”.  This is also the reason why it is impossible to have a custom firmware above 3.56, simply because since the 3.56 version, Sony have fixed their ECDSA algorithm implementation and used new keys for which it is impossible to find the private key.. if there was a way to find that key, then the security of every computer, website, system may be compromised since a lot of systems are relying on ECDSA for their security, and it is impossible to crack.

Finally! I hope this makes the whole algorithm clearer to many of you.. I know that this is still very complicated and hard to understand. I usually try to make things easy to understand for non technical people, but this algorithm is too complex to be able to explain in any simpler terms. After all that’s why I prefer to call it the MFET algorithm (Mathematics For Extra Terrestrials) 🙂

But if you are a developer or a mathematician or someone interested in learning about this because you want to help or simple gain knowledge, then I’m sure that this contains enough information for you to get started or to at least understand the concept behind this unknown beast called “ECDSA”.

That being said, I’d like to thank a few people who helped me understand all of this, one particularly who wishes to remain anonymous, as well as the many wikipedia pages I linked to throughout this article, and Avi Kak thanks to his paper explaining the mathematics behind ECDSA, and from which I have taken those graph images aboves.

P.s: In this article, I used ’20 bytes’ in my text to talk about the ECDSA signature because that’s what is usually used as it matches the SHA1 hash size of 20 bytes and that’s what the PS3 security uses, but the algorithm itself can be used with any size of numbers. There may be other inaccuracies in this article, but like I said, I’m not an expert, I just barely learned all of this in the past week.

Status update on the PS3 4.0 HEN

Here’s a “quick” status update on the 4.00 HEN (Homebrew ENabler) for PS3.

Following my clarifications from almost 2 months ago here, there has been a lot of progress. We have not been slacking off, we’re a group of about 10 developers working together for the last 2 months, for sometimes 15 hours everyday in order to bring back homebrew support to the latest version of the PS3.

There are three major parts to the HEN, first, getting the packages to install on the PS3, that part is done, completed, tested, debugged, etc.. the second part is to get the apps to run, that one still has major issues… the last part is something I will not discuss for now (it’s a surprise) but it’s about 60% to 70% done (and it has nothing to do with peek&poke and has nothing to do with backup managers or anything like that. This is and will stay a piracy-free solution for the PS3).

Now, running apps is the biggest challenge that we’ve been working on for the past 2 months. As some of you know, if you’ve been following me on Twitter, we originally had hoped for Mathieulh to give us the “npdrm hash algorithm” that was necessary to run the apps, but he was reluctant, he kept doing his usual whore so people would kiss his feet (or something else) so he’d feel good about himself. But in the end, he said that he refuses to give us the needed “npdrm hash algorithm” to make it work… So what I initially thought would be “this will be released next week” ended up taking a lot more time than expected, and we’re still nowhere near ready to make it work.

Mathieulh kept tossing his usual “riddles” which he thinks are “very helpful for those who have a brain”, and which pisses off anyone who actually does… so he told us that the solution to all our problems was to look in appldr of the 3.56 firmware.. and that it was something lv1 was sending appldr which made the “hash check” verified or not… so we spent one month and a lot of sweat and after killing a few of our brain cells out of exhaustion, we finally concluded that it was all bullshit. After one month of reading assembly code and checking and double-checking our results, we finally were able to confirm that that hash algorithm was NOT in the 3.56 firmware like he told us (at all).

He said  that it was an AES OMAC hash, but after tracking all the uses of the OMAC functions in appldr, we found that it was not used for the “hash”…  he then said “oh, I meant HMAC“, so we do that again and again come up with the same conclusion, then we’re sure it’s not in appldr, and then he says “ah no, it’s in lv1“.. have a look for yourself to what he decided to write : http://www.ps3devwiki.com/index.php?title=Talk:KaKaRoTo_Kind_of_%C2%B4Jailbreak%C2%B4

That happened after the huge twitter fight I had with him for being his usual arrogant ass and claiming that he “shared” something (For your information, the code that he shared was not his own, I have proof of that too (can’t show you the proof because even if I don’t respect him, I gave him my word to not share what he gave me, and I respect my word) since he forgot to remove the name of the original developer from one of the files… also it was completely useless and was not used at all, just made me waste a day reading the crappy undocumented code. So why is he still trying to force his “advice” through these riddles even after we had that fight? Well to sabotage us and make us lose all those months of hard work!

So anyways, we had all accepted that Mathieulh was full of shit (we knew before, but we gave him the benefit of the doubt) and decided to continue working without considering any of his useless riddles. So we then tried to exploit/decrypt the 3.60+ firmware in order to get the algorithm from there.

Now, a few more weeks later, we finally have succeeded in fully understanding that missing piece from the “npdrm hash algorithm”,  and here it is for everyone’s pleasure with some prerequisite explanation :

A game on the PS3 is an executable file in a format called a “SELF“file (kind of like .exe on windows), those “self” files are cryptographically signed and encrypted.. For PSN games (games that do not run from a bluray disc), they need to have an additional security layer called “NPDRM”. So a “npdrm self” is basically an executable that is encrypted and signed, then re-encrypetd again with some additional information. On 3.55 and lower, we were able to encrypt and sign our own self files so they would look like original (made by sony) “npdrm self” files, and the PS3 would run them without problem. However, it wasn’t really like an original file.. a real NPDRM self file had some additional information that the PS3 simply ignored, it did not check for that information, so we could put anything in it, and it worked. Since the 3.60 version, the PS3 now also validates this additional information, so it can now differentiate between NPDRM self files created by sony and the ones that we create ourselves for homebrew. That’s the “npdrm hash algorithm” that we have been trying to figure out, because once we can duplicate that information in the proper manner, then the PS3 will again think that those files are authentic and will let us play them.

Another important point to explain, I said a few times that the files are “signed”.. this means that there is an “ECDSA signature” in the file which the PS3 can verify. The ECDSA signature is something that allows the PS3 to verify if the file has been modified or not.. it is easy to validate the signature, but impossible to create one without having access to the “private keys” (think of it like a real signature, you can see your dad’s signature and recognize it, but you can’t sign it exactly like him, and you can recognize if your brother tried to forge his signature). So how were we able to sign the self files that were properly authenticated on 3.55? That’s because this “ECDSA signature” is just a very complicated mathematical equation (my head still hurts trying to fully understand it, but I might blog about it in the future and try to explain it in simple terms if people are interested you can learn about it here), and one very important part of this mathematical equation is that you need to use a random number to generate the signature, but Sony had failed and used the same number every time.. by doing that, it was easy to just find the private key (which allows us to forge perfectly the signature) by doing some mathematical equation on it. So to summarize, a “signed file” is a file which is digitally signed with an “ECDSA signature” that cannot be forged, unless you have the “private key” for it, which is impossible to obtain usually, but we were able to obtain it because Sony failed in implementing it properly.

Now, back on topic.. so what is this missing “npdrm hash algorithm” that we need? well it turns out that the “npdrm self” has a second signature, so it’s a “encrypted and signed self file” with an additional layer of security (the NPDRM layer) which re-encrypts it and re-signs it again. That second signature was not verified in 3.55 and is now verified since the 3.60 version of the PS3 firmware.

One important thing to note is that Sony did NOT make the same mistake with this signature, they always used a random number, so it it technically impossible to figure out the private key for it. To be more exact, this is the exact same case as the .pkg packages you install on the PS3, you need to patch the firmware (making it cfw) so that those .pkg files can be installed, and that’s because the .pkg files are signed with an ECDSA signature for which no one was able to get the private key. That’s why we call them “pseudo-retail packages” or “unsigned packages”.

The signature on the NPDRM self file uses the exact same ECDSA curve and the same key as the one used in PS3 .pkg files, so no one has (or could have) the private key for it. What this means is that, even though we finally figured out the missing piece and we now know how the NPDRM self is built, we simply cannot duplicate it.

The reason we wasted 2 months on this is because Mathieulh lied by saying that he can do it.. remember when the 4.0 was out and I said “I can confirm that my method still works” then he also confirmed that his “npdrm hash algorithm” still works too? well he didn’t do anything to confirm, he just lied about it because there is no way that he could have verified it because he doesn’t have the private key.

I said I will provide proof of the lies that Mathieulh gave us, so here they are : he said it’s in 3.56, that was a lie, he said it’s an AES OMAC, that was a lie,  he said it’s an HMAC, that was a lie, he said it’s in appldr, that was a lie, he said it’s in lv1, that was a lie, he said that he can do it, that was a lie, he said that “it takes one hour to figure it out if you have a brain”, that was a lie, he said that he verified it to work on 4.0, that was a lie, he said that he had the algorithm/keys, that was a lie, he said that once we know the algorithm used, we can reproduce it, that was a lie, he kept referring to it as “the hash”, that was wrong. The proof ? It’s an ECDSA signature, it’s not a hash (two very different terms for different things), it was verified by vsh.self, it was not in lv2, or lv1, or appldr, and the private key is unaccessible, so there is no way he could build his own npdrm self files. Now you know the real reason why he refused to “share” what he had.. it’s because he didn’t have it…

So why do all this? was it because his arrogance didn’t allow him to admit not knowing something? or was it because he wanted to make us lose all this time? To me, it looks like pure sabotage, it was misleading information to steer us away from the real part of the code that holds the solution…. That is of course, if we are kind enough to assume that he knew what/where it was in the first place.  In the end, he wasn’t smart enough to only lie about things that we could not verify.. now we know (we always knew, but now we have proof to back it) that he’s a liar, and I do not think that anyone will believe his lies anymore.

 

Enough talking about liars and drama queens, back to the 4.0 HEN solution… so what next? well, we now know that we can’t sign the file, so we can’t run our apps on 3.60+ (it can work on 3.56 though). What we will do is look for a different way, a completely new exploit that would allow the files we install to actual run on the PS3. We will also be looking for possible “signature collisions” and for that we will need the help of the community, hopefully there is a collision (same random number used twice) which will allow us to calculate the private key, and if that happens, then we can move forward with a release.

When will the “jailbreak” be released? If I knew, I’d tell you, but I don’t know.. I would have said in last november, then december, then before christmas, then before new year, etc… but as you can see, it’s impossible to predict what we will find.. we might get lucky and have it ready in a couple of days, or we may not and it will not be ready for another couple of months.. so all you need to do is : BE PATIENT (and please stop asking me about an estimated release date)!

I would like to thank the team who helped on this task for all this time and who never got discouraged, and I’d like to thank an anonymous contributor who recently joined us and who was instrumental in figuring it all out. We all believe that freedom starts with knowledge, and that knowledge should be open and available to all, that is why we are sharing this information with the world. We got the confirmation (by finding the public key used and verifying the signatures) yesterday and since sharing this information will not help Sony in any way to block our efforts in a future release, we have decided to share it with you.  We believe in transparency, we believe in openness, we believe in a free world, and we want you to be part of it.

If you want to know more about this ECDSA signature algorithm, I tried to explain it in a blog post here, also, you can read this interesting paper that explains it in detail, and you can also watch Team Fail0verflow’s CCC presentation that first explained Sony’s mistake in their implementation, which made custom firmwares possible.

 

Thanks for reading,

KaKaRoTo

 

GstFilters library released!

After the various blog posts about it, and the talk I gave at the GStreamer Conference, there was a lot of interest in the GstFilters library that I’ve been working on. The original plan was for it to get merged into gst-plugins-base, however, it seems like that’s not going to happen. The GStreamer developers would prefer seeing some of its features integrated into the core, but they don’t want the library itself. So I have finally decided to release it as a standalone package so everyone interested can already start using it.

As features from GstFilters will slowly get merged into the core of GStreamer, I will adapt the library to make use of these new features, reducing its internal code. However I believe it is still very useful to have Gstfilters as it’s a very simple library for those who are not familiar with GStreamer. Also the concept of the ‘filters’ is very different from the GstElements because an element can only be added once in a pipeline but filters can be added any number of times in a pipeline (a GstFilter doesn’t represent an actual element, it’s more like a helper function for “create and link these elements for me”). Also the points I’ve made about the steep learning curve and the robustness checks will still be valid even after the Gst core makes dynamic pipeline modifications easier.

GstFilters are now released and will be hosted on freedesktop.org under Farstream’s project. While Farstream users will be the most interested in this library and it is very useful for VoIP/Farstream users, it can also be used for non VoIP applications.

On a similar note, the Farsight-Utils library and API that I presented at the GStreamer Conference has been modified to make it even simpler. The library has been renamed into Farstream-IO since it basically takes care of all the Input/Output to the Farstream conference. The new API is based on a single object now, a FsIoPipeline that you create (which is a subclass of GstPipeline) and to which you register the FsConference/FsSession/FsStream. All the methods from the previous Farsight-Utils classes (FsuConference, FsuSession and FsuStream) will stay the same but will be merged into this single FsIoPipeline class, making everything easier and you’d only need to keep track of a single object.

The FsIo API will be merged into Farstream and released for the next version.

Here is the link to the new GstFilters page : http://www.freedesktop.org/wiki/Software/GstFilters 

And you can get the release tarball from here : http://freedesktop.org/software/farstream/releases/gstfilters/

And browse its documentation here : http://www.freedesktop.org/software/farstream/apidoc/gstfilters/ 

 

ExpoLibre 2011 in Talca/Chile

Hi all,

About 2 weeks ago, I was in Talca, Chile for the ExpoLibre 2011 conference. It was really awesome, I had one of the best experiences as a speaker!

One of the particularities of that conference, is that it’s organized by the university and its target audience is students, teachers and enthusiasts in open source. The majority of the attendees were not open source developers, but they were people who wanted to learn more about it.
For that reason, this was my very first “motivational talk” rather than my usual technical talks that I’ve given in the past, and I loved it!

Another interesting point was that the audience was mostly speaking Spanish, and not everyone understood English, so I had my colleagues (Reynaldo Verdejo and Thibault Saunier) there to translate what I was saying. That created a very pleasant experience as I had time to relax between each slide while they were translating, and it also made the talk more casual and interactive. I wasn’t nervous for the first time, and it felt great! 🙂

After the talk, I received some very interesting questions and I thoroughly enjoyed answered everyone of them. I saw a lot of people who were interested and I felt like I connected with everyone and I was able to touch them with my ideas. If I was able to change at least one attendee’s perception of open source, and hopefully get them involved in various FLOSS projects, then my mission is a success!

Today, the organizers of the ExpoLibre conference sent me the video recording of my talk, and I’ve shared it on youtube so everyone can listen to what I had stay. I hope everyone enjoys it as much as I enjoyed doing it.

On a final note, I’d like to say that Chile is a beautiful country. I stayed there for almost two weeks, and even though travel from/to Canada is a pain, it was totally worth it! I can’t wait for the next opportunity for me to go there.

Update : Some people complained about the rhythm being broken because of the translation to spanish,  so I asked here for anyone who wants to contribute, to edit the video and crop the non-english sections, so english-only speaking people can view the talk in one constant rhythm/flow without the interruptions by the translators.

Patrick Donnelly, one of the people who saw the video (and my request for an edit) did it and commented below  with a link to an english-only version of my talk (the intro and questions part were left untouched at my request). Here it is for those who need it :

 

And here is the original, unedited version of my talk I gave, enjoy it!

Ps: The video I tried to show to the audience (around 6:30) which did not work, was this one : http://www.youtube.com/watch?v=20ClL3mL8Gc

And here are the slides used during the talk, in PDF format : http://people.collabora.co.uk/~kakaroto/expolibre-2011.pdf 

 

KaKaRoTo

 

Clarifications about 3.73 (and 4.0) “jailbreak”

Update:
I tested the jailbreak on the latest firmware 4.0 since it was released and I can confirm that it still works.

Hi all,

I’ve been flooded with questions on twitter and I’ve read many posts on news sites and  I’ve seen some stuff being said on IRC and I thought I needed to clarify a few things…

First of all, I didn’t expect to see my tweet front paged on all ps3 hacking news sites.. although I should have expected it.. but anyways, the “jailbreak” is not ready to be used, at all. I only tweeted that because I was excited having it working and I wanted to share my excitement with everyone. But this is a bit equivalent to the day I released that create_cfw.sh script that created the very first CFW/MFW but it still took a couple of months before a real, easy, multiplatform and fully fledged solution was released : PS3MFW.

We are currently at the same state, I have the proof of concept, it works, but a solution that anyone can use where they just click a button and their PS3 gets jailbroken is still far from ready.

I’ve seen people say (and even write it in their front page news) that I’ll release it in two weeks after I come back from vacation. That is not true and I never said that. What I said was that for the next 2 weeks, the project is on hold until I get back.. but when I get back, then I will continue working on it, and it will then take some more time before it’s ready and released.

Some asked if it’s based on what gitbrew was doing/suggesting or if I used someone else’s exploit or work. No, this solution is my own idea and 100% my own implementation. However, the actual solution for the full jailbreak involves some components on which I will not work, and I expect/hope that someone else will provide the solution for that.

Some speculated it might be what I spoke about back in March which I later said I wasn’t pursuing by lack of motivation.. and yes, you are right. The same hack I had in March is still valid today, I told a few people about it (rms, Mathieulh, an0nym0us, and a couple more), but no one was interested in pursuing it further and actually exploiting that flaw (mainly because it requires a huge amount of work to get a proof of concept working). 10 days ago (I started on the 11th), I got bored and decided to start poking at it again, and yesterday (a lot faster than I thought it would take), I got my first pkg installed on 3.73 firmware.

On twitter, I said “do not update if you are on 3.55”, I said that in response to someone who said he would update.  Because of that, people speculated that you need to be on 3.55 first, and then install something before doing the upgrade. No, that’s not it, that would be useless. The purpose of my solution is to jailbreak a ps3 that is already on 3.73 firmware and which had never been jailbroken before. I told people not to update because, first of all, it’s not yet ready, and second of all, the 3.55 firmware gives you a lot more possibilities than what can be achieved on 3.73.

So what is this jailbreak? I won’t say because I don’t want Sony to block it in a firmware update (and yes, they potentially could) before it’s even released (and yes, I will release it when it’s ready). But I will explain this to you : in order to run your homebrew apps, you need two things. First, to be able to install them on the ps3, and second to be able to run it once installed. I did only one of these two things.

Some may say it’s not a real jailbreak, but the way I see it, there are three ‘jails’ on the ps3, I broke the first one which prevents you from installing anything, so now you can install your .pkg, great, but it won’t run, that’s the second jail. The third jail is being able to modify the firmware (peek&poke).

The second jail (running apps) is something that can be done, but it’s not my area of expertise (npdrm algo), so I will not be working on that. I am waiting for someone else to achieve it (some have succeeded but do not wish to release it, at least not for now) then I will release.

The third jail (modifying the firmware) is not possible with my method, this means that you will  not have a “CFW”, you will run your homebrew applications and games on an official firmware. This also means that without peek&poke support, none of the backup managers will work. So, again, my solution is piracy-free, and as always, I do not plan on working on a way to enable piracy (or even legal backups).

Overall, the purpose will be to allow people who are on 3.73 firmware to enjoy the homebrew games that were released, to play a bit with Eskiss, and to use Showtime for playing their movies. This should be more than enough for everyone.

Finally, I will conclude by replying to another question I received : Do you accept donations? The answer is yes. I do accept donations but I do not seek them out. I will include a donate button to the bottom of this post, so if anyone wishes to donate, they can do so, however, I want to make it clear that whether or not you donate does not and will not affect in any way, the release, or the progress of the work I’m doing. If you donate, you would do it as a sign of appreciation of my efforts, and not in exchange of any favors or anything crazy like that.

That’s about it I think… If you have any more questions, please refrain from asking them, I get enough as it is already.. I also said everything I needed to say and I don’t want to give any more information than that (for now).

KaKaRoTo