Please don't try to specify everything using BDD. You'll end up with a horribly fine-grained backlog that takes ages to maintain and which will still bear no resemblance to the real project that emerges.
Something I've done - and which works very well with BDD later on - is to look at the high-level capabilities which the system needs to provide. A capability is something that a user will be able to do, or which the system can do. This obviously means business capabilities, but it can include technical capabilities, such as performance, integration with 3rd party systems, etc. As a guideline, we had about 30 cards for a 2-year enterprise project.
Next, put a big red dot on anything which is new or unknown. These are your most risky areas.
If you want to, you can roughly estimate the relative size of the capabilities in points, the same way you would estimate stories, but bigger (use multiples of 10 at least). I started with the smallest at 20, then the biggest at 400, then found one in the middle and went from there.
When you're done, double everything with a red dot unless you can think of why the risk isn't that bad.
This will give you a really good idea of how complex and risky the project is compared to similar projects you've done, and you'll be able to estimate the approximate cost much more easily. It will also let you spend your money and the customer's on producing software instead of arguing about scope. If you have trouble estimating it, find some people who've done similar projects. You can also use the capabilities to define a minimum release, which will be easier to estimate and also represent less risk and faster return to the customer.
My last piece of advice is to work with reasonable customers who would rather produce useful stuff and address the real risk together than argue about who is responsible for defining the nebulous future.
For further reading, this is an article I wrote a while back on this technique (we were referring to capabilities as themes or feature sets then). Please also read Dan North's posts on the Perils of Estimation and Deliberate Discovery.