Never use 777 for directories on your live server, but on your own machine, sometimes we need to do more than 775, because
chmod -R 775 storage
7 - Owner can write
7 - Group can write
5 - Others cannot write!
If your webserver is not running as Vagrant, it will not be able to write to it, so you have 2 options:
chmod -R 777 storage
or change the group to your webserver user, supposing it's www-data:
chown -R vagrant:www-data storage
Hope this helps!