From 3baeb11a8fbcfcdbc31976d421f17b85503b3ecd Mon Sep 17 00:00:00 2001
From: WuKong <rebirthmonkey@gmail.com>
Date: Fri, 4 Sep 2015 09:25:34 +0200
Subject: init attribute-based encryption

Change-Id: Iba1a3d722110abf747a0fba366f3ebc911d25b25
---
 moon-abe/cpabe-0.11/policy_lang.y | 637 ++++++++++++++++++++++++++++++++++++++
 1 file changed, 637 insertions(+)
 create mode 100644 moon-abe/cpabe-0.11/policy_lang.y

(limited to 'moon-abe/cpabe-0.11/policy_lang.y')

diff --git a/moon-abe/cpabe-0.11/policy_lang.y b/moon-abe/cpabe-0.11/policy_lang.y
new file mode 100644
index 00000000..5528033b
--- /dev/null
+++ b/moon-abe/cpabe-0.11/policy_lang.y
@@ -0,0 +1,637 @@
+%{
+#include <stdio.h>
+#include <ctype.h>
+#include <string.h>
+#include <stdlib.h>
+#include <stdint.h>
+#include <glib.h>
+#include <pbc.h>
+
+#include "common.h"
+#include "policy_lang.h"
+
+typedef struct
+{
+	uint64_t value;
+	int bits; /* zero if this is a flexint */
+}
+sized_integer_t;
+
+typedef struct
+{
+	int k;               /* one if leaf, otherwise threshold */
+	char* attr;          /* attribute string if leaf, otherwise null */
+	GPtrArray* children; /* pointers to bswabe_policy_t's, len == 0 for leaves */
+}
+cpabe_policy_t;
+
+cpabe_policy_t* final_policy = 0;
+
+int yylex();
+void yyerror( const char* s );
+sized_integer_t* expint( uint64_t value, uint64_t bits );
+sized_integer_t* flexint( uint64_t value );
+cpabe_policy_t* leaf_policy( char* attr );
+cpabe_policy_t* kof2_policy( int k, cpabe_policy_t* l, cpabe_policy_t* r );
+cpabe_policy_t* kof_policy( int k, GPtrArray* list );
+cpabe_policy_t* eq_policy( sized_integer_t* n, char* attr );
+cpabe_policy_t* lt_policy( sized_integer_t* n, char* attr );
+cpabe_policy_t* gt_policy( sized_integer_t* n, char* attr );
+cpabe_policy_t* le_policy( sized_integer_t* n, char* attr );
+cpabe_policy_t* ge_policy( sized_integer_t* n, char* attr );
+%}
+
+%union
+{
+	char* str;
+	uint64_t nat;
+  sized_integer_t* sint;
+	cpabe_policy_t* tree;
+	GPtrArray* list;
+}
+
+%token <str>  TAG
+%token <nat>  INTLIT
+%type  <sint> number
+%type  <tree> policy
+%type  <list> arg_list
+
+%left OR
+%left AND
+%token OF
+%token LEQ
+%token GEQ
+
+%%
+
+result: policy { final_policy = $1; }
+
+number:   INTLIT '#' INTLIT          { $$ = expint($1, $3); }
+        | INTLIT                     { $$ = flexint($1);    }
+
+policy:   TAG                        { $$ = leaf_policy($1);        }
+        | policy OR  policy          { $$ = kof2_policy(1, $1, $3); }
+        | policy AND policy          { $$ = kof2_policy(2, $1, $3); }
+        | INTLIT OF '(' arg_list ')' { $$ = kof_policy($1, $4);     }
+        | TAG '=' number             { $$ = eq_policy($3, $1);      }
+        | TAG '<' number             { $$ = lt_policy($3, $1);      }
+        | TAG '>' number             { $$ = gt_policy($3, $1);      }
+        | TAG LEQ number             { $$ = le_policy($3, $1);      }
+        | TAG GEQ number             { $$ = ge_policy($3, $1);      }
+        | number '=' TAG             { $$ = eq_policy($1, $3);      }
+        | number '<' TAG             { $$ = gt_policy($1, $3);      }
+        | number '>' TAG             { $$ = lt_policy($1, $3);      }
+        | number LEQ TAG             { $$ = ge_policy($1, $3);      }
+        | number GEQ TAG             { $$ = le_policy($1, $3);      }
+        | '(' policy ')'             { $$ = $2;                     }
+
+arg_list: policy                     { $$ = g_ptr_array_new();
+                                       g_ptr_array_add($$, $1); }
+        | arg_list ',' policy        { $$ = $1;
+                                       g_ptr_array_add($$, $3); }
+;
+
+%%
+
+sized_integer_t*
+expint( uint64_t value, uint64_t bits )
+{
+	sized_integer_t* s;
+
+	if( bits == 0 )
+		die("error parsing policy: zero-length integer \"%llub%llu\"\n",
+				value, bits);
+	else if( bits > 64 )
+		die("error parsing policy: no more than 64 bits allowed \"%llub%llu\"\n",
+				value, bits);
+
+	s = malloc(sizeof(sized_integer_t));
+	s->value = value;
+	s->bits = bits;
+
+	return s;
+}
+
+sized_integer_t*
+flexint( uint64_t value )
+{
+	sized_integer_t* s;
+
+	s = malloc(sizeof(sized_integer_t));
+	s->value = value;
+	s->bits = 0;
+
+	return s;
+}
+
+void
+policy_free( cpabe_policy_t* p )
+{
+	int i;
+
+	if( p->attr )
+		free(p->attr);
+
+	for( i = 0; i < p->children->len; i++ )
+		policy_free(g_ptr_array_index(p->children, i));
+	g_ptr_array_free(p->children, 1);
+
+	free(p);
+}
+
+cpabe_policy_t*
+leaf_policy( char* attr )
+{
+	cpabe_policy_t* p;
+
+	p = (cpabe_policy_t*) malloc(sizeof(cpabe_policy_t));
+	p->k = 1;
+	p->attr = attr;
+	p->children = g_ptr_array_new();
+
+	return p;
+}
+
+cpabe_policy_t*
+kof2_policy( int k, cpabe_policy_t* l, cpabe_policy_t* r )
+{
+	cpabe_policy_t* p;
+
+	p = (cpabe_policy_t*) malloc(sizeof(cpabe_policy_t));
+	p->k = k;
+	p->attr = 0;
+	p->children = g_ptr_array_new();
+	g_ptr_array_add(p->children, l);
+	g_ptr_array_add(p->children, r);
+
+	return p;
+}
+
+cpabe_policy_t*
+kof_policy( int k, GPtrArray* list )
+{
+	cpabe_policy_t* p;
+
+	if( k < 1 )
+		die("error parsing policy: trivially satisfied operator \"%dof\"\n", k);
+	else if( k > list->len )
+		die("error parsing policy: unsatisfiable operator \"%dof\" (only %d operands)\n",
+				k, list->len);
+	else if( list->len == 1 )
+		die("error parsing policy: identity operator \"%dof\" (only one operand)\n", k);
+
+	p = (cpabe_policy_t*) malloc(sizeof(cpabe_policy_t));
+	p->k = k;
+	p->attr = 0;
+	p->children = list;
+
+	return p;
+}
+
+char*
+bit_marker( char* base, char* tplate, int bit, char val )
+{
+	char* lx;
+	char* rx;
+	char* s;
+
+ 	lx = g_strnfill(64 - bit - 1, 'x');
+	rx = g_strnfill(bit, 'x');
+	s = g_strdup_printf(tplate, base, lx, !!val, rx);
+	free(lx);
+	free(rx);
+
+	return s;
+}
+
+cpabe_policy_t*
+eq_policy( sized_integer_t* n, char* attr )
+{
+	if( n->bits == 0 )
+		return leaf_policy
+			(g_strdup_printf("%s_flexint_%llu", attr, n->value));
+	else
+		return leaf_policy
+			(g_strdup_printf("%s_expint%02d_%llu", attr, n->bits, n->value));
+
+	return 0;
+}
+
+cpabe_policy_t*
+bit_marker_list( int gt, char* attr, char* tplate, int bits, uint64_t value )
+{
+	cpabe_policy_t* p;
+	int i;
+
+	i = 0;
+	while( gt ? (((uint64_t)1)<<i & value) : !(((uint64_t)1)<<i & value) )
+		i++;
+
+	p = leaf_policy(bit_marker(attr, tplate, i, gt));
+	for( i = i + 1; i < bits; i++ )
+		if( gt )
+			p = kof2_policy(((uint64_t)1<<i & value) ? 2 : 1, p,
+											leaf_policy(bit_marker(attr, tplate, i, gt)));
+		else
+			p = kof2_policy(((uint64_t)1<<i & value) ? 1 : 2, p,
+											leaf_policy(bit_marker(attr, tplate, i, gt)));
+
+	return p;
+}
+
+cpabe_policy_t*
+flexint_leader( int gt, char* attr, uint64_t value )
+{
+	cpabe_policy_t* p;
+	int k;
+
+	p = (cpabe_policy_t*) malloc(sizeof(cpabe_policy_t));
+	p->attr = 0;
+	p->children = g_ptr_array_new();
+
+	for( k = 2; k <= 32; k *= 2 )
+		if( ( gt && ((uint64_t)1<<k) >  value) ||
+				(!gt && ((uint64_t)1<<k) >= value) )
+			g_ptr_array_add
+				(p->children, leaf_policy
+				 (g_strdup_printf(gt ? "%s_ge_2^%02d" : "%s_lt_2^%02d", attr, k)));
+
+	p->k = gt ? 1 : p->children->len;
+
+	if( p->children->len == 0 )
+	{
+		policy_free(p);
+		p = 0;
+	}
+	else if( p->children->len == 1 )
+	{
+		cpabe_policy_t* t;
+		
+		t = g_ptr_array_remove_index(p->children, 0);
+		policy_free(p);
+		p = t;
+	}
+	
+	return p;
+}
+
+cpabe_policy_t*
+cmp_policy( sized_integer_t* n, int gt, char* attr )
+{
+	cpabe_policy_t* p;
+	char* tplate;
+
+	/* some error checking */
+
+	if( gt && n->value >= ((uint64_t)1<<(n->bits ? n->bits : 64)) - 1 )
+		die("error parsing policy: unsatisfiable integer comparison %s > %llu\n"
+				"(%d-bits are insufficient to satisfy)\n", attr, n->value,
+				n->bits ? n->bits : 64);
+	else if( !gt && n->value == 0 )
+		die("error parsing policy: unsatisfiable integer comparison %s < 0\n"
+				"(all numerical attributes are unsigned)\n", attr);
+	else if( !gt && n->value > ((uint64_t)1<<(n->bits ? n->bits : 64)) - 1 )
+		die("error parsing policy: trivially satisfied integer comparison %s < %llu\n"
+				"(any %d-bit number will satisfy)\n", attr, n->value,
+				n->bits ? n->bits : 64);
+
+	/* create it */
+
+	/* horrible */
+	tplate = n->bits ?
+		g_strdup_printf("%%s_expint%02d_%%s%%d%%s", n->bits) :
+		strdup("%s_flexint_%s%d%s");
+	p = bit_marker_list(gt, attr, tplate, n->bits ? n->bits :
+											(n->value >= ((uint64_t)1<<32) ? 64 :
+											 n->value >= ((uint64_t)1<<16) ? 32 :
+											 n->value >= ((uint64_t)1<< 8) ? 16 :
+											 n->value >= ((uint64_t)1<< 4) ?  8 :
+											 n->value >= ((uint64_t)1<< 2) ?  4 : 2), n->value);
+	free(tplate);
+
+	if( !n->bits )
+	{
+		cpabe_policy_t* l;
+		
+		l = flexint_leader(gt, attr, n->value);
+		if( l )
+			p = kof2_policy(gt ? 1 : 2, l, p);
+	}
+
+	return p;
+}
+
+cpabe_policy_t*
+lt_policy( sized_integer_t* n, char* attr )
+{
+	return cmp_policy(n, 0, attr);
+}
+
+cpabe_policy_t*
+gt_policy( sized_integer_t* n, char* attr )
+{
+	return cmp_policy(n, 1, attr);
+}
+
+cpabe_policy_t*
+le_policy( sized_integer_t* n, char* attr )
+{
+	n->value++;
+	return cmp_policy(n, 0, attr);
+}
+
+cpabe_policy_t*
+ge_policy( sized_integer_t* n, char* attr )
+{
+	n->value--;
+	return cmp_policy(n, 1, attr);
+}
+
+char* cur_string = 0;
+
+#define PEEK_CHAR ( *cur_string ? *cur_string     : EOF )
+#define NEXT_CHAR ( *cur_string ? *(cur_string++) : EOF )
+
+int
+yylex()
+{
+  int c;
+	int r;
+
+  while( isspace(c = NEXT_CHAR) );
+
+	r = 0;
+  if( c == EOF )
+    r = 0;
+	else if( c == '&' )
+		r = AND;
+	else if( c == '|' )
+		r = OR;
+	else if( strchr("(),=#", c) || (strchr("<>", c) && PEEK_CHAR != '=') )
+		r = c;
+	else if( c == '<' && PEEK_CHAR == '=' )
+	{
+		NEXT_CHAR;
+		r = LEQ;
+	}
+	else if( c == '>' && PEEK_CHAR == '=' )
+	{
+		NEXT_CHAR;
+		r = GEQ;
+	}
+	else if( isdigit(c) )
+	{
+		GString* s;
+
+		s = g_string_new("");
+		g_string_append_c(s, c);
+		while( isdigit(PEEK_CHAR) )
+			g_string_append_c(s, NEXT_CHAR);
+
+		sscanf(s->str, "%llu", &(yylval.nat));
+
+		g_string_free(s, 1);
+		r = INTLIT;
+	}
+	else if( isalpha(c) )
+	{
+		GString* s;
+
+		s = g_string_new("");
+		g_string_append_c(s, c);
+
+		while( isalnum(PEEK_CHAR) || PEEK_CHAR == '_' )
+			g_string_append_c(s, NEXT_CHAR);
+
+		if( !strcmp(s->str, "and") )
+		{
+			g_string_free(s, 1);
+			r = AND;
+		}
+		else if( !strcmp(s->str, "or") )
+		{
+			g_string_free(s, 1);
+			r = OR;
+		}
+		else if( !strcmp(s->str, "of") )
+		{
+			g_string_free(s, 1);
+			r = OF;
+		}
+		else
+		{
+			yylval.str = s->str;
+			g_string_free(s, 0);
+			r = TAG;
+		}
+	}
+	else
+		die("syntax error at \"%c%s\"\n", c, cur_string);
+
+	return r;
+}
+
+void
+yyerror( const char* s )
+{
+  die("error parsing policy: %s\n", s);
+}
+
+#define POLICY_IS_OR(p)  (((cpabe_policy_t*)(p))->k == 1 && ((cpabe_policy_t*)(p))->children->len)
+#define POLICY_IS_AND(p) (((cpabe_policy_t*)(p))->k == ((cpabe_policy_t*)(p))->children->len)
+
+void
+merge_child( cpabe_policy_t* p, int i )
+{
+	int j;
+	cpabe_policy_t* c;
+
+	c = g_ptr_array_index(p->children, i);
+	if( POLICY_IS_AND(p) )
+	{
+		p->k += c->k;
+		p->k--;
+	}
+
+	g_ptr_array_remove_index_fast(p->children, i);
+	for( j = 0; j < c->children->len; j++ )
+		g_ptr_array_add(p->children, g_ptr_array_index(c->children, j));
+
+	g_ptr_array_free(c->children, 0);
+	free(c);
+}
+
+void
+simplify( cpabe_policy_t* p )
+{
+	int i;
+
+	for( i = 0; i < p->children->len; i++ )
+		simplify(g_ptr_array_index(p->children, i));
+
+	if( POLICY_IS_OR(p) )
+		for( i = 0; i < p->children->len; i++ )
+			if( POLICY_IS_OR(g_ptr_array_index(p->children, i)) )
+				merge_child(p, i);
+
+	if( POLICY_IS_AND(p) )
+		for( i = 0; i < p->children->len; i++ )
+			if( POLICY_IS_AND(g_ptr_array_index(p->children, i)) )
+				merge_child(p, i);
+}
+
+int
+cmp_tidy( const void* a, const void* b )
+{
+	cpabe_policy_t* pa;
+	cpabe_policy_t* pb;
+
+	pa = *((cpabe_policy_t**) a);
+	pb = *((cpabe_policy_t**) b);
+
+	if(      pa->children->len >  0 && pb->children->len == 0 )
+		return -1;
+	else if( pa->children->len == 0 && pb->children->len >  0 )
+		return 1;
+	else if( pa->children->len == 0 && pb->children->len == 0 )
+		return strcmp(pa->attr, pb->attr);
+	else
+		return 0;	
+}
+
+void
+tidy( cpabe_policy_t* p )
+{
+	int i;
+
+	for( i = 0; i < p->children->len; i++ )
+		tidy(g_ptr_array_index(p->children, i));
+
+	if( p->children->len > 0 )
+		qsort(p->children->pdata, p->children->len,
+					sizeof(cpabe_policy_t*), cmp_tidy);
+}
+
+char*
+format_policy_postfix( cpabe_policy_t* p )
+{
+	int i;
+	char* r;
+	char* s;
+	char* t;
+
+	if( p->children->len == 0 )
+		return strdup(p->attr);
+
+	r = format_policy_postfix(g_ptr_array_index(p->children, 0));
+	for( i = 1; i < p->children->len; i++ )
+	{
+		s = format_policy_postfix(g_ptr_array_index(p->children, i));
+		t = g_strjoin(" ", r, s, (char*) 0);
+		free(r);
+		free(s);
+		r = t;
+	}
+	
+	t = g_strdup_printf("%s %dof%d", r, p->k, p->children->len);
+ 	free(r);
+
+	return t;
+}
+
+/*
+	Crufty.
+*/
+int
+actual_bits( uint64_t value )
+{
+	int i;
+
+	for( i = 32; i >= 1; i /= 2 )
+		if( value >= ((uint64_t)1<<i) )
+			return i * 2;
+
+	return 1;
+}
+
+/*
+	It is pretty crufty having this here since it is only used in
+	keygen. Maybe eventually there will be a separate .c file with the
+	policy_lang module.
+*/
+void
+parse_attribute( GSList** l, char* a )
+{
+	if( !strchr(a, '=') )
+		*l = g_slist_append(*l, a);
+	else
+	{
+		int i;
+		char* s;
+		char* tplate;
+		uint64_t value;
+		int bits;
+
+		s = malloc(sizeof(char) * strlen(a));
+
+		if( sscanf(a, " %s = %llu # %u ", s, &value, &bits) == 3 )
+		{
+			/* expint */
+
+			if( bits > 64 )
+				die("error parsing attribute \"%s\": 64 bits is the maximum allowed\n",
+						a, value, bits);
+
+			if( value >= ((uint64_t)1<<bits) )
+				die("error parsing attribute \"%s\": value %llu too big for %d bits\n",
+						a, value, bits);
+
+			tplate = g_strdup_printf("%%s_expint%02d_%%s%%d%%s", bits);
+			for( i = 0; i < bits; i++ )
+				*l = g_slist_append
+					(*l, bit_marker(s, tplate, i, !!((uint64_t)1<<i & value)));
+			free(tplate);
+
+			*l = g_slist_append
+				(*l, g_strdup_printf("%s_expint%02d_%llu", s, bits, value));
+		}
+		else if( sscanf(a, " %s = %llu ", s, &value) == 2 )
+		{
+			/* flexint */
+
+			for( i = 2; i <= 32; i *= 2 )
+				*l = g_slist_append
+					(*l, g_strdup_printf
+					 (value < ((uint64_t)1<<i) ? "%s_lt_2^%02d" : "%s_ge_2^%02d", s, i));
+
+			for( i = 0; i < 64; i++ )
+				*l = g_slist_append
+					(*l, bit_marker(s, "%s_flexint_%s%d%s", i, !!((uint64_t)1<<i & value)));
+
+			*l = g_slist_append
+				(*l, g_strdup_printf("%s_flexint_%llu", s, value));
+		}
+		else
+			die("error parsing attribute \"%s\"\n"
+					"(note that numerical attributes are unsigned integers)\n",	a);
+
+ 		free(s);
+	}	
+}
+
+char*
+parse_policy_lang( char* s )
+{
+	char* parsed_policy;
+
+	cur_string = s;
+
+	yyparse();
+ 	simplify(final_policy);
+ 	tidy(final_policy);
+	parsed_policy = format_policy_postfix(final_policy);
+
+	policy_free(final_policy);
+
+	return parsed_policy;
+}
-- 
cgit 1.2.3-korg